Utilitas Algorithmica (UA)

ISSN: xxxx-xxxx (print)

Utilitas Algorithmica (UA) is a premier, open-access international journal dedicated to advancing algorithmic research and its applications. Launched to drive innovation in computer science, UA publishes high-impact theoretical and experimental papers addressing real-world computational challenges. The journal underscores the vital role of efficient algorithm design in navigating the growing complexity of modern applications. Spanning domains such as parallel computing, computational geometry, artificial intelligence, and data structures, UA is a leading venue for groundbreaking algorithmic studies.

Yanfang Zhang1, Qingde Kang2
1College of Mathematics and Statistics Hebei University of Economics and Business Shijiazhuang 050061, P.R. China
2Institute of Mathematics, Hebei Normal University Shijiazhuang 050024, P.R. China
Abstract:

Let \( K_v \) be the complete graph with \( v \) vertices. Let \( G \) be a finite simple graph. A \( G \)-decomposition of \( K_v \), denoted by \((v, G, 1)\)-GD, is a pair \((X, \mathcal{B})\), where \( X \) is the vertex set of \( K_v \), and \(\mathcal{B}\) is a collection of subgraphs of \( K_v \), called blocks, such that each block is isomorphic to \( G \). In this paper, the discussed graphs are \( G_i \), \( i = 1, 2, 3, 4 \), where \( G_i \) are four kinds of graphs with eight vertices and eight edges. We obtain the existence spectrum of \((v, G_i, 1)\)-GD.

Beata Bényi1, Eétvés Jézsef Fdiskola2
1Bolyai Institute, University of Szeged Vértanuk tere 1., Szeged, Hungary 6720.
2Bajesy-Zsilinszky u. 14., Baja, Hungary 6500.
Abstract:

We present a simple bijection between the set of triangulations of a convex polygon and the set of \(312\)-avoiding permutations.

Mustapha Chellali1, Nader Jafari Rad2
1LAMDA-RO Laboratory, Department of Mathematics University of Blida. B.P. 270, Blida, Algeria.
2Department of Mathematics, Shahrood University of Technology, Shahrood, Iran and School of Mathematics, Institute for Research in Fundamental Sciences (IPM) P.O. Box 19395-5746, Tehran, Iran
Abstract:

A \({2-rainbow\; dominating\; function}\) of a graph \( G \) is a function \( g \) that assigns to each vertex a set of colors chosen from the set \( \{1, 2\} \) so that for each vertex \( v \) with \( g(v) = \emptyset \) we have \( \cup_{u \in N(v)} g(u) = \{1, 2\} \). The minimum of \( g(V(G)) = \sum_{v \in V(G)} |g(v)| \) over all such functions is called the \({2-rainbow \;domination\; number}\) \( \gamma_{r2}(G) \). A \(2\)-rainbow dominating function \( g \) of a graph \( G \) is independent if no two vertices assigned non-empty sets are adjacent. The \({independent \;2-rainbow\; domination\; number}\) \( i_{r2}(G) \) is the minimum weight of an independent \(2\)-rainbow dominating function of \( G \). In this paper, we study independent \(2\)-rainbow domination in graphs. We present some bounds and relations with other domination parameters.

Eric Andrews1, Daniel Johnston 1, Ping Zhang1
1Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA
Abstract:

For a connected graph \( G \) of order at least \( 3 \) and an integer \( k \geq 2 \), a \({twin\; edge}\) \( k \)-coloring of \( G \) is a proper edge coloring of \( G \) with the elements of \( \mathbb{Z}_k \), so that the induced vertex coloring in which the color of a vertex \( v \) in \( G \) is the sum (in \( \mathbb{Z}_k \)) of the colors of the edges incident with \( v \) is a proper vertex coloring. The minimum \( k \) for which \( G \) has a twin edge \( k \)-coloring is called the \({twin \;chromatic\; index}\) of \( G \) and is denoted by \( \chi_t'(G) \). It was conjectured that \( \Delta(T) \leq \chi_t'(T) \leq 2 + \Delta(T) \) for every tree of order at least \( 3 \), where \( \Delta(T) \) is the maximum degree of \( T \). This conjecture is verified for several classes of trees, namely brooms, double stars, and regular trees.

Chira Lumduanhom1, Eric Andrews2, Ping Zhang2
1Department of Mathematics Srinakharinwirot University, Sukhumvit Soi 23, Bangkok, 10110, Thailand
2Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
Abstract:

For a nontrivial connected graph \( G \), let \( c: V(G) \to \mathbb{Z}_2 \) be a vertex coloring of \( G \) where \( c(v) \neq 0 \) for at least one vertex \( v \) of \( G \). Then the coloring \( c \) induces a new coloring \( \sigma: V(G) \to \mathbb{Z}_2 \) of \( G \) defined by
\[
\sigma(v) = \sum_{u \in N[v]} c(u)
\]
where \( N[v] \) is the closed neighborhood of \( v \) and addition is performed in \( \mathbb{Z}_2 \). If \( \sigma(v) = 0 \in \mathbb{Z}_2 \) for every vertex \( v \) in \( G \), then the coloring \( c \) is called a (modular) monochromatic \( (2,0) \)-coloring of \( G \). A graph \( G \) having a monochromatic \( (2,0) \)-coloring is a (monochromatic) \( (2,0) \)-colorable graph. The minimum number of vertices colored \( 1 \) in a monochromatic \( (2,0) \)-coloring of \( G \) is the \( (2,0) \)-chromatic number of \( G \) and is denoted by \( \chi_{(2,0)}(G) \). For a \( (2,0) \)-colorable graph \( G \), the monochromatic \( (2,0) \)-spectrum \( S_{(2,0)}(G) \) of \( G \) is the set of all positive integers \( k \) for which exactly \( k \) vertices of \( G \) can be colored \( 1 \) in a monochromatic \( (2,0) \)-coloring of \( G \). Monochromatic \( (2,0) \)-spectra are determined for several well-known classes of graphs. If \( G \) is a connected graph of order \( n \geq 2 \) and \( a \in S_{(2,0)}(G) \), then \( a \) is even and \( 1 \leq |S_{(2,0)}(G)| \leq \left\lfloor \frac{n}{2} \right\rfloor \). It is shown that for every pair \( k,n \) of integers with \( 1 \leq k \leq \left\lfloor \frac{n}{2} \right\rfloor \), there is a connected graph \( G \) of order \( n \) such that \( |S_{(2,0)}(G)| = k \). A set \( S \) of positive even integers is \( (2,0) \)-realizable if \( S \) is the monochromatic \( (2,0) \)-spectrum of some connected graph. Although there are infinitely many non-\((2,0)\)-realizable sets, it is shown that every set of positive even integers is a subset of some \( (2,0) \)-realizable set. Other results and questions are also presented on \( (2,0) \)-realizable sets in graphs.

Eric Andrews1, Ping Zhang1
1 Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
Abstract:

For two graphs \( H \) and \( G \), a decomposition \( \mathcal{D} = \{H_1, H_2, \ldots, H_k, R\} \) of \( G \) is called an \( H \)-maximal \( k \)-decomposition if \( H_i \cong H \) for \( 1 \leq i \leq k \) and \( R \) contains no subgraph isomorphic to \( H \). Let \(\text{Min}(G, H)\) and \(\text{Max}(G, H)\) be the minimum and maximum \( k \), respectively, for which \( G \) has an \( H \)-maximal \( k \)-decomposition. A graph \( G \) without isolated vertices is said to possess the intermediate decomposition property if for each connected graph \( G \) and each integer \( k \) with \(\text{Min}(G, H) \leq k \leq \text{Max}(G, H)\), there exists an \( H \)-maximal \( k \)-decomposition of \( G \). For a set \( S \) of graphs and a graph \( G \), a decomposition \( \mathcal{D} = \{H_1, H_2, \ldots, H_k, R\} \) of \( G \) is called an \( S \)-maximal \( k \)-decomposition if \( H_i \cong H \) for some \( H \in S \) for each integer \( i \) with \( 1 \leq i \leq k \) and \( R \) contains no subgraph isomorphic to any subgraph in \( S \). Let \(\text{Min}(G, S)\) and \(\text{Max}(G, S)\) be the minimum and maximum \( k \), respectively, for which \( G \) has an \( S \)-maximal \( k \)-decomposition. A set \( S \) of graphs without isolated vertices is said to possess the intermediate decomposition property if for every connected graph \( G \) and each integer \( k \) with \(\text{Min}(G, S) \leq k \leq \text{Max}(G, S)\), there exists an \( S \)-maximal \( k \)-decomposition of \( G \). While all those graphs of size \( 3 \) have been determined that possess the intermediate decomposition property, as have all sets consisting of two such graphs, here all remaining sets of graphs having size \( 3 \) that possess the intermediate decomposition property are determined.

Eric Andrews1, Zhenming Bi1, Ping Zhang1
1 Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA
Abstract:

An Eulerian graph \( G \) of size \( m \) is said to satisfy the Eulerian Cycle Decomposition Conjecture if the minimum number of odd cycles in a cycle decomposition of \( G \) is \( a \), the maximum number of odd cycles in a cycle decomposition is \( b \), and \( \ell \) is an integer such that \( a \leq \ell \leq b \) where \( \ell \) and \( m \) are of the same parity, then there is a cycle decomposition of \( G \) with exactly \( \ell \) odd cycles. Several regular complete \( 5 \)-partite graphs are shown to have this property.

Dinesh G. Sarvate1, Li Zhang2
1Department of Mathematics College of Charleston Charleston, SC 29424 l U.S.A.
2 Department of Mathematics and Computer Science The Citadel Charleston, SC 29409
Abstract:

An \( H_3 \) graph is a multigraph on three vertices with double edges between two pairs of distinct vertices and a single edge between the third pair. To settle the \( H_3 \) decomposition problem completely, one needs to complete the decomposition of a \( 2K_{10t+5} \) into \( H_3 \) graphs. In this paper, we present two new construction methods for such decompositions, resulting in previously unknown decompositions for \( v = 15, 25, 35, 45 \) and two new infinite families.

E. A. Yfantis1, A. Fayed1
1ICIS Laboratory Computer Science Department, College of Engineering University of Nevada, Las Vegas Las Vegas, NV, 89154-4019
Abstract:

Analog modulation has served us very well over the years. Digital modulation is an improvement over analog modulation because it provides better bandwidth utilization over analog modulation, less power for signal propagation, it is natural for packet transmission, forward error correction, automatic repeat request, encryption, compression, and signal transformation so that it looks like noise to the adversary. Digital wireless communication is an enormous area that is rapidly growing. Digital communication is a field in which theoretical ideas have had an unusually powerful impact on system design and practice. In this research paper we provide a digital modulation algorithm for efficient transmission based on circular probability distribution theory.

Barbara M. Anthony1, Richard Denman1
1Department of Mathematics and Computer Science Southwestern University Georgetown, Texas, US
Abstract:

A primitive hypergraph is a hypergraph with maximum cardinality three and maximum degree three such that every \(3\)-edge is adjacent only to \(2\)-edges and is incident only to vertices of degree two. Deciding the bicolorability of a primitive hypergraph is NP-complete (a straightforward consequence of results in [14]). We provide sufficient conditions, similar to the Sterboul conditions proved by Défossez [5], for the existence of a bicoloring of a primitive hypergraph, and we provide a polynomial algorithm for bicoloring a primitive hypergraph if those conditions hold. We then draw a connection between this algorithm and the well-known necessary and sufficient conditions given by Berge [1] for maximal matchings in graphs, which leads to a characterization of bicolorability of primitive hypergraphs.

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;