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.

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

L. Asgharsharghi1, D. Kiani1,2
1Faculty of Mathematics and Computer Science, Amirkabir University of Technology, P.O, Box 15875-4413, Tehran, Iran
2Schoo!l of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran
Abstract:

Let \(G\) be a graph of order \(n\) and let \(\mu\) be an eigenvalue of multiplicity \(m\). A star complement for \(\mu\) in \(G\) is an induced subgraph of \(G\) of order \(n-m\) with no eigenvalue \(\mu\). Some general observations concerning graphs with the complete tripartite graph \(K_{r,s,t}\) as a star complement are made. We study the maximal regular graphs which have \(K_{r,s,t}\) as a star complement for eigenvalue \(\mu\). The results include a complete analysis of the regular graphs which have \(K_{n,n,n}\) as a star complement for \(\mu = 1\). It turns out that some well-known strongly regular graphs are uniquely determined by such a star complement.

Hung-Lin Fu1, Yuan-Hsun Lo1
1Department of Applied Mathematics National Chiao Tung University Hsinchu, Taiwan 30050
Abstract:

In this paper, we first prove that if the edges of \(K_{2m}\) are properly colored by \(2m-1\) colors in such a way that any two colors induce a 2-factor of which each component is a 4-cycle, then \(K_{2m}\) can be decomposed into \(m\) isomorphic multicolored spanning trees. Consequently, we show that there exist three disjoint isomorphic multicolored spanning trees in any properly \((2m-1)\)-edge-colored \(K_{2m-1}\) for \(m \geq 14\).

Qigang Yu1, Zhongxun Zhu1
1Faculty of Mathematics and Statistics, South Central University for Nationalities, Wuhan 430074, P.R. China
Abstract:

The Merrifield-Simmons index, denoted by \(i(G)\), of a graph \(G\) is defined as the total number of its independent sets. A fully loaded unicyclic graph is a unicyclic graph with the property that there is no vertex with degree less than \(3\) in its unique cycle. Let \(\mathcal{U}_n^1\) be the set of fully loaded unicyclic graphs. In this paper, we determine graphs with the largest, second-largest, and third-largest Merrifield-Simmons index in \(\mathcal{U}_n^1\).

Shubo Chen1,2, Weijun Liu2
1School of Mathematics and Computer Science, Hunan City University, Yiyang, Hunan 413000, P. R.China
2College of Mathematics and statistics, Central South University, Changsha 410075, P. R. China
Abstract:

For a graph \(G = (V, E)\), the modified Schultz index of \(G\) is defined as \(S^0(G) = \sum\limits_{\{u,v\} \subset V(G)} (d_G(u) – d_G(v)) d_{G}(u, v)\), where \(d_G(u)\) (or \(d(u)\))is the degree of the vertex \(u\) in \(G\), and \(d_{G}(u, v)\) is the distance between \(u\) and \(v\). The first Zagreb index \(M_1\) is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index \(M_2\) is equal to the sum of the products of the degrees of pairs of adjacent vertices. In this paper, we present a unified approach to investigate the modified Schultz index and Zagreb indices of tricyclic graphs. The tricyclic graph with \(n\) vertices having minimum modified Schultz index and maximum Zagreb indices are determined.

Abstract:

Let \(T = (V, A)\) be a (finite) tournament and \(k\) be a non-negative integer. For every subset \(X\) of \(V\)\), the subtournament \(T[X] = (X, A \cap (X \times X))\) of \(T\), induced by \(X\), is associated. The dual tournament of \(T\), denoted by \(T^*\), is the tournament obtained from \(T\) by reversing all its arcs. The tournament \(T\) is self-dual if it is isomorphic to its dual. \(T\) is \((-k)\)-self-dual if for each set \(X\) of \(k\) vertices, \(T[V \setminus X]\) is self-dual. \(T\) is strongly self-dual if each of its induced subtournaments is self-dual. A subset \(I\) of \(V\) is an interval of \(T\) if for \(a,b \in I\) and for \(x \in V \setminus I\), \((a,x) \in A\) if and only if \((b,x) \in A\). For instance, \(\emptyset\), \(V\), and \(\{x\}\), where \(x \in V\), are intervals of \(T\) called trivial intervals. \(T\) is indecomposable if all its intervals are trivial; otherwise, it is decomposable. A tournament \(T’\), on the set \(V\), is \((-k)\)-hypomorphic to \(T\) if for each set \(X\) on \(k\) vertices, \(T[V \setminus X]\) and \(T'[V \setminus X]\) are isomorphic. The tournament \(T\) is \((-k)\)-reconstructible if each tournament \((-k)\)-hypomorphic to \(T\) is isomorphic to it.

Suppose that \(T\) is decomposable and \(|V| \geq 9\). In this paper, we begin by proving the equivalence between the \((-3)\)-self-duality and the strong self-duality of \(T\). Then we characterize each tournament \((-3)\)-hypomorphic to \(T\). As a consequence of this characterization, we prove that if there is no interval \(X\) of \(T\) such that \(T[X]\) is indecomposable and \(|V \setminus X| \leq 2\), then \(T\) is \((-3)\)-reconstructible. Finally, we conclude by reducing the \((-3)\)-reconstruction problem.

Haiyan Li1, Chunhui Lai1
1Department of Mathematics and Information Science, Zhangzhou Teachers College, Zhangzhou, Fujian 363000, P. R. of CHINA.
Abstract:

For a given graph \(H\), a graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) is said to be potentially \(H\)-graphic if there exists a realization of \(\pi\) containing \(H\) as a subgraph. In this paper, we characterize the potentially \(C_{2,6}\)-graphic sequences. This characterization partially answers Problem 6 in Lai and Hu [12].

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;