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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 115-131
- Published: 31/08/2015
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 97-114
- Published: 31/08/2015
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 79-95
- Published: 31/08/2015
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 61-77
- Published: 31/08/2015
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 53-59
- Published: 31/08/2015
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 43-51
- Published: 31/08/2015
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 27-41
- Published: 31/08/2015
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 15-25
- Published: 31/08/2015
Let \( D \) be a strongly connected oriented graph with vertex-set \( V \) and arc-set \( A \). The distance from a vertex \( u \) to another vertex \( v \), \( d(u,v) \), is the minimum length of oriented paths from \( u \) to \( v \). Suppose \( B = \{b_1, b_2, b_3, \ldots, b_k\} \) is a nonempty ordered subset of \( V \). The representation of a vertex \( v \) with respect to \( B \), \( r(v|B) \), is defined as a vector \( (d(v,b_1), d(v,b_2), \ldots, d(v,b_k)) \). If any two distinct vertices \( u,v \) satisfy \( r(u|B) \neq r(v|B) \), then \( B \) is said to be a resolving set of \( D \). If the cardinality of \( B \) is minimum, then \( B \) is said to be a basis of \( D \), and the cardinality of \( B \) is called the directed metric dimension of \( D \).
Let \( G \) be the underlying graph of \( D \) admitting a \( C_n \)-covering. A \( C_n \)-simple orientation is an orientation on \( G \) such that every \( C_n \) in \( D \) is strongly connected. This paper deals with metric dimensions of oriented wheels, oriented fans, and amalgamation of oriented cycles, all of which admit \( C_n \)-simple orientations.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 094
- Pages: 3-14
- Published: 31/08/2015
A Stanton-type graph \( S(n, m) \) is a connected multigraph on \( n \) vertices such that for a fixed integer \( m \) with \( n – 1 \leq m \leq \binom{n}{2} \), there is exactly one edge of multiplicity \( i \) (and no others) for each \( i = 1, 2, \ldots, m \). In a recent paper, the authors decomposed \( \lambda K_{n} \) (for the appropriate minimal values of \( \lambda \)) into two of the four possible types of \( S(4, 3) \)’s. In this note, decompositions of \( \lambda K_{n} \) (for the appropriate minimal values of \( \lambda \)) into the remaining two types of \( S(4, 3) \)’s are given.
- Research article
- Full Text
- Ars Combinatoria
- Volume 122
- Pages: 439-447
- Published: 31/07/2015
In this work, we consider the generalized Genocchi numbers and polynomials. However, we introduce an analytic interpolating function for the generalized Genocchi numbers attached to \(\chi\) at negative integers in the complex plane, and also we define the Genocchi \(p\)-adic \(L\)-function. As a result, we derive the value of the partial derivative of the Genocchi \(p\)-adic \(l\)-function at \(s = 0\).




