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.

Cheng Yeaw Ku1, Kok Bin Wong2
1Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang link, Singapore 637371, Singapore
2Institute of Mathematical Sciences, Faculty of Science, Universiti Malaya, 50603 Kuala Lumpur, Malaysia
Abstract:

A graph \(G\) is said to be a an interval graph, if for each vertex \(u\) of \(G\), one can assign a set \(A_u\) which is a finite union of intervals on the real line such that \(u\) is adjacent to \(v\) in \(G\) if and only if \(A_u\cap A_v\neq\varnothing\). In this paper, we introduce a class of intersection graphs and show that it is equivalent to the class of interval graphs. We also investigate interval numbers of certain intersection graphs and establish several related results.

Fumiya Takahata1, Atsuhiro Nakamoto2
1Graduate School of Environment and Information Sciences, Yokohama National University, Yokohama 240-8501, Japan
2Faculty of Environment and Information Sciences, Yokohama National University, Yokohama 240-8501, Japan
Abstract:

For a graph \(G=(V(G), E(G))\), a subset \(S \subset V(G)\) is a bipartite dominating set if every vertex in \(G-S\) is adjacent to a vertex in \(S\), and if the subgraph of \(G\) induced by \(S\) is bipartite. The bipartite domination number of \(G\), denoted by \(\gamma_{bip}(G)\), is the minimum cardinality of all bipartite dominating sets of \(G\). Xi and Yue [4] claimed that for every 2-connected outerplanar \(n\)-vertex graph \(G\), \(\gamma_{bip}(G) \leq \lceil \frac n 3 \rceil\), and that this bound is sharp. In this paper, correcting the result, we prove that \(\gamma_{bip}(G) \leq \lceil \frac 38 n \rceil\), where this bound is sharp.

Muhammed Sabeel K1, Krishnan Paramasivam2
1Department of Mathematics, Government Engineering College, Palakkad 678633, India
2Department of Mathematics, National Institute of Technology Calicut, Kozhikode 673601, India
Abstract:

In this article, we obtain the determining number and the metric dimension of the zero-divisor graph of the ring of integers modulo \(n\) and of non-Boolean semisimple rings. For Boolean rings, an upper bound for these parameters is established. While the determining number and metric dimension of \(\Gamma(\mathbb{Z}_n)\) are known in the literature, we provide an alternative derivation based on a structural decomposition of the graph via generalized join. This approach offers a direct and unified method to compute these parameters. Further, we determine these parameters for joins of vertex-transitive graphs and investigate certain questions concerning the relationship between determining number and metric dimension.

Farzaneh Ramezani1, Yousef Bagheri1
1Department of Mathematics, K.N.Toosi University of Technology, P. O. Box 16765–3381, Tehran, Iran
Abstract:

Motivated from the concept of strong regularity in the graph theory, few varieties of definitions for strongly regular signed graphs have been introduced. The initial one, which is due to Zaslavsky and the others are given by Stanic and Ramezani. The definition given by Stanic covers all the others. In this paper we provide some constructions for each of the definitions.

Kayla Wager1, John T. Saccoman1
1Department of Mathematics & Computer Science, Seton Hall University, South Orange, NJ 07079, U.S.A.
Abstract:

Threshold graphs are graphs whose node set can be partitioned into a clique and an independent set, with the additional property that for each pair of nodes, one’s neighborhood is a subset of the other’s neighborhood. Threshold graphs have been well-studied in graph theory, but not much is known about multigraphs that are underlying threshold. Proper threshold graphs are those in which all nodes in the independent set have the same degree. In this paper, we present a formula for the eigenvalues of a particular class of multigraphs that are underlying proper threshold.

Toufik Mansour1, Amir Safadi1
1Department of Mathematics, University of Haifa, 3103301 Haifa, Israel
Abstract:

In this paper, we enumerate restricted-growth words of type \(B\) associated with signed set partitions with respect to several statistics related to levels, ascents, and descents. For each case, we investigate these words according to four types of statistics and study the total of each statistic individually. Furthermore, we determine both the ordinary and the exponential generating functions for the total of each statistic under consideration.

Mohsen Aliabadi1
1Department of Mathematics, Clayton State University, Morrow, GA, USA
Abstract:

Hall’s theorem on differences of bijections characterizes the multisets \(\{a_1,\ldots,a_{|G|}\}\) in a finite abelian group \(G\) that can be written in the form \( a_i=b_i-c_i, \) where both \(b_1,\ldots,b_{|G|}\) and \(c_1,\ldots,c_{|G|}\) are enumerations of \(G\). The necessary and sufficient condition is the zero-sum condition \( a_1+\cdots+a_{|G|}=0. \) This paper studies the corresponding problem for finite nonabelian groups, with differences replaced by quotients. Thus we ask when a multiset \(A\) of cardinality \(|G|\) can be represented as \( A=\{b(i)c(i)^{-1}:1\le i\le |G|\}, \) where \(b\) and \(c\) are bijections onto \(G\). Passing to the abelianization gives a necessary condition, namely that the product of the images of the elements of \(A\) is trivial in \(G_{\rm ab}\). We show that this condition is not sufficient in general, even when the elements of \(A\) admit an ordering whose product is the identity in \(G\). The main structural result is a cycle-tiling criterion: quotient-realizability is equivalent to a decomposition of \(A\) into product-one words whose partial-product sets tile \(G\) by right translates. The use of permutation cycles is standard, but the criterion translates quotient-realizability into an exact tiling condition. We then use this criterion to construct a counterexample in \(S_3\), and we extend the same obstruction to infinitely many finite nonabelian groups.

Wen-Fong Ke1, Hubert Kiechle2
1Department of Mathematics, National Cheng Kung University, Tainan, Taiwan
2Universität Hamburg, Fachbereich Mathematik, Bundesstr, 55, Hamburg, Germany
Abstract:

We investigate diagonal equations \(ax^{m}+by^{m}-cz^{m}=1\) over finite fields \(F\) using combinatorial designs naturally associated with \(F\). Building on prior work that resolved the case \(a=b=c=1\), we obtain exact formulas for the solutions when \(a=1\) and \(b=c\), under circularity assumptions. For general coefficients, we present an algorithm that determines whether a given instance can be reduced to the settled cases, or else identifies it as requiring brute-force computation.

Bilal Brahimi1, Rebiha Benterki2
1Laboratory of Mathematics and Applied Sciences, Department of Mathematics and Computer Science, University of Ghardaia 47000, Algeria
2Mathematical Analysis and Applications Laboratory, Department of Mathematics, University Mohamed El Bachir El Ibrahimi of Bordj Bou Arréridj 34000, El Anasser, Algeria
Abstract:

In this paper, we expand our interest in the 16th Hilbert’s problem to acquire a comprehensive understanding of the maximum number of crossing limit cycles in \(\mathbb{R}^3\), specifically within a class of three- dimensional discontinuous piecewise differential system generated by two arbitrary Euler systems separated by the unit sphere \(\mathbb{S}^2=\{ (x,y,z) \in\mathbb{R}^3; x^2 + y^2 + z^2 = 1\}\).

Mithra R.1, Ragukumar P.1
1Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Vellore, Tamil Nadu, India-632014
Abstract:

Let \(G\) be a graph with no isolated vertices. A \(k\)-coupon coloring of \(G\) is an assignment of colors from \([k]=\{1,2,\ldots,k\}\) to the vertices of \(G\) such that the neighborhood of every vertex contains all colors from \([k]\). The maximum integer \(k\) for which a \(k\)-coupon coloring exists is called the coupon coloring number of \(G\), and is denoted by \(\chi_c(G)\). In this paper, we investigate coupon coloring in inflated graphs arising from various classes of graphs. In addition, we introduce new graph operations based on inflation and study their effect on the existence and behavior of coupon colorings. Our results contribute to a deeper understanding of how inflation based graph operations influence coupon coloring.

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;