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.

Martin Bata1, Dafik 2,3, Mirka Miller2,4, Joe Ryan2
1Department of Appl. Mathematics Technical University, Kosice, Slovak Republic
2School of Information Technology and Mathematical Sciences University of Ballarat, Australia
3Department. of Mathematics Education Universitas Jember, Indonesia
4Department of Mathematics University of West Bohemia, Plzei, Czech Republic
Abstract:

Let \( G = (V, E) \) be a finite graph, where \( V(G) \) and \( E(G) \) are the (non-empty) sets of vertices and edges of \( G \). An \((a, d)\)-\({edge-antimagic\; total\; labeling}\) is a bijection \( \beta \) from \( V(G) \cup E(G) \) to the set of consecutive integers \( \{1, 2, \dots, |V(G)| + |E(G)|\} \) with the property that the set of all the edge-weights, \( w(uv) = \beta(u) + \beta(uv) + \beta(v) \), for \( uv \in E(G) \), is \( \{a, a + d, a + 2d, \dots, a + (|E(G)| – 1)d\} \), for two fixed integers \( a > 0 \) and \( d \geq 0 \). Such a labeling is super if the smallest possible labels appear on the vertices. In this paper, we investigate the existence of super \((a, d)\)-edge-antimagic total labelings for disjoint unions of multiple copies of a regular caterpillar.

Kim Marshall1, Joe Ryan1
1School of Information Technology and Mathematical Sciences The University of Ballarat Ballarat, Victoria 3353, Australia
Abstract:

The term mode graph was introduced by Boland, Kaufman, and Panrong to define a connected graph \( G \) such that, for every pair of vertices \( v, w \) in \( G \), the number of vertices with eccentricity \( e(v) \) is equal to the number of vertices with eccentricity \( e(w) \). As a natural extension to this work, the concept of an antimode graph was introduced to describe a graph for which, if \( e(v) \neq e(w) \), then the number of vertices with eccentricity \( e(v) \) is not equal to the number of vertices with eccentricity \( e(w) \). In this paper, we determine the existence of some classes of antimode graphs, namely equisequential and \((a, d)\)-antimode graphs.

Dafik 1,2, Mirka Miller1,3, Joe Ryan1, Martin Baéa1,4
1School of Information Technology and Mathematical Sciences University of Ballarat, Australia
2Department. of Mathematics Education Universitas Jember, Indonesia
3Department of Mathematics University of West Bohemia, Plzcii, Czech Republic
4Technical University, Kosice, Slovak Republic
Abstract:

By an \((a, d)\)-edge-antimagic total labeling of a graph \( G(V, E) \), we mean a bijective function \( f \) from \( V(G) \cup E(G) \) onto the set \( \{1, 2, \dots, |V(G)| + |E(G)|\} \) such that the set of all the edge-weights, \( w(uv) = f(u) + f(uv) + f(v) \), for \( uv \in E(G) \), is \( \{a, a+d, a+2d, \dots, a + (|E(G)| – 1)d\} \), for two integers \( a > 0 \) and \( d \geq 0 \).

In this paper, we study the edge-antimagic properties for the disjoint union of complete \( s \)-partite graphs.

G. Aranjo1, R.M. Figueroa-Centeno2, R. Ichishima3, F.A. Muntaner-Batle4
1Instituto de Matematicas, Universidad Nacional Auténoma de México, 04510 México D.F.
2Mathematics Departament, University of Hawaii-Hilo, 200 W. Kawili St. Ililo, HI 96720, U.S.A.
3College of Humanities and Sciences, Nihon University, 3-25-40 Sakurajosui Setagaya-ku, Tokyo 156-8550, Japan
4Departament de Matematica Aplicada i Telematica, Universitat Politécnica de Catalunya, 08071 Barcelona, Spain.
Abstract:

We study the number of super edge-magic (bipartite) graphs from an asymptotic point of view.

Guillermo Pineda-Villavicencio1,2, Mirka Miller1,3
1School of Information Technology and Mathematical Sciences University of Ballarat, Ballarat, Australia
2Department of Computer Science, University of Oriente, Santiago de Cuba, Cuba
3Department of Mathematics, University of West Bohemia,Pilsen, Cacch Republic
Abstract:

It is well known that apart from the Petersen graph, there are no Moore graphs of degree 3. As a cubic graph must have an even number of vertices, there are no graphs of maximum degree 3 and \(\delta\) vertices less than the Moore bound, where \(\delta\) is odd. Additionally, it is known that there exist only three graphs of maximum degree 3 and 2 vertices less than the Moore bound. In this paper, we consider graphs of maximum degree 3, diameter \( D \geq 2 \), and 4 vertices less than the Moore bound, denoted as \((3, D, 4)\)-graphs. We obtain all non-isomorphic \((3, D, 4)\)-graphs for \( D = 2 \). Furthermore, for any diameter \( D \), we consider the girth of \((3, D, 4)\)-graphs. By a counting argument, it is easy to see that the girth is at least \( 2D – 2 \). The main contribution of this paper is that we prove that the girth of a \((3, D, 4)\)-graph is at least \( 2D – 1 \). Finally, for \( D > 4 \), we conjecture that the girth of a \((3, D, 4)\)-graph is \( 2D \).

Claude Levesque1
1Départment de Mathématiques et de Statistique Université Laval, Québec, Canada G1IK 7P4
Abstract:

A fast direct method for obtaining the incidence matrix of a finite projective plane of order \( n \) via \( n-1 \) mutually orthogonal \( n \times n \) Latin squares is described. Conversely, \( n-1 \) mutually orthogonal \( n \times n \) Latin squares are directly exhibited from the incidence matrix of a projective plane of order \( n \). A projective plane of order \( n \) can also be described via a digraph complete set of Latin squares, and a new procedure for doing this will also be described.

Landang Yuan1, Qingde Kang2
1College of Occupation Technology, Hebei Normal University, Shijiazhuang 050031, P. R. China
2Institute of Math., Hebei Normal University, Shijiazhuang 050016, P. R. China
Abstract:

Let \(K_v\) be a complete graph with \(v\) vertices, and \(G = (V(G), E(G))\) be a finite simple graph. A \(G\)-design \(G-GD_\lambda(v)\) 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\) and any two distinct vertices in \(K_v\) are joined in exactly \(\lambda\) blocks of \(\mathcal{B}\). In this paper, the existence of graph designs \(G-GD_\lambda(v)\), \(\lambda > 1\), for eight graphs \(G\) with six vertices and eight edges is completely solved.

Bing Chen1, Shenggui Zhang1
1Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P.R. China
Abstract:

A \({weighted \;graph}\) is one in which every edge \(e\) is assigned a nonnegative number \(w(e)\), called the \({weight}\) of \(e\). The \({weight\; of \;a \;cycle}\) is defined as the sum of the weights of its edges. The \({weighted \;degree}\) of a vertex is the sum of the weights of the edges incident with it. In this paper, motivated by a recent result of Fujisawa, we prove that a \(2\)-connected weighted graph \(G\) contains either a Hamilton cycle or a cycle of weight at least \(2m/3\) if it satisfies the following conditions:
\((1)\) The weighted degree sum of every three pairwise nonadjacent vertices is at least \(m\);\((2)\)In each induced claw and each induced modified claw of \(G\), all edges have the same weight.This extends a theorem of Zhang, Broersma and Li.

Jun-Ming Xu1, Min Lu1
1Department of Mathematics University of Science and Technology of China Hefei, Anhui, 230026, China
Abstract:

The \({restricted edge-connectivity}\) of a graph is an important parameter to measure fault-tolerance of interconnection networks. This paper determines that the restricted edge-connectivity of the de Bruijn digraph \(B(d,n)\) is equal to \(2d – 2\) for \(d \geq 2\) and \(n \geq 2\) except \(B(2,2)\). As consequences, the super edge-connectedness of \(B(d,n)\) is obtained immediately.

J. Barat1, P.P. Varju2
1Technical University of Denmark, Department of Mathematics, B.303. 2800 Lyngby, Denmark
2Analysis and Stochastics Research Group of the Hungarian Academy of Sciences, Bolyai institute, University of Szeged, Aradi vértanuk tere 1. Szeged, 6720 Hungary
Abstract:

An edge coloring of a graph is called \({square-free}\) if the sequence of colors on certain walks is not a square, that is not of the form \(x_1, \ldots, x_m, x_{1}, \ldots, x_m\) for any \(m \in \mathbb{N}\). Recently, various classes of walks have been suggested to be considered in the above definition. We construct graphs, for which the minimum number of colors needed for a square-free coloring is different if the considered set of walks vary, solving a problem posed by Brešar and Klavžar. We also prove the following: if an edge coloring of \(G\) is not square-free (even in the most general sense), then the length of the shortest square walk is at most \(8|E(G)|^2\). Hence, the necessary number of colors for a square-free coloring is algorithmically computable.

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;