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.

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.

Sigit Pancahayani1, Rinovia Simanjuntak1
1Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung, Bandung 40132, Indonesia
Abstract:

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.

Abstract:

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.

Serkan Araci1, Erdogan Sen2
1DEPARTMENT OF ECONOMICS, FACULTY OF ECONOMICS, ADMINISTRATIVE AND SOCIAL SCIENCE, HASAN KALYONCU UNIVERSITY, TR-27410 GAZIANTEP, TURKEY
2DEPARTMENT OF MATHEMATICS, FACULTY OF SCIENCE AND LETTERS, NAMIK KEMAL UNIVERSITY, 59030 TekirnpaG, TURKEY; DEPARTMENT OF MATHE- MATICS ENGINEERING, ISTANBUL TECHNICAL UNIVERSITY, MASLAK, 34469 Is- TANBUL, TURKEY
Abstract:

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\).

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;