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.

Sin-Min Lee1, Ling Wang1, Ken Nowak2, Wandi Wei3
1Department of Computer Science San Jose State University San Jose, California 95192 U.S.A.
2Department of Civil Engineering San Jose State University San Jose, California 95192 U.S.A.
3Center for Cryptology and Information Security Florida Atlantic University, – Boca Raton, FL33431
Abstract:

A \( (p,q) \)-graph \( G \) is said to be \(\textbf{edge-graceful}\) if the edges can be labeled by \( 1,2,\ldots, q \) so that the vertex sums are distinct, mod \( p \). It is shown that if a tree \( T \) is edge-graceful, then its order must be odd. Lee conjectured that all trees of odd orders are edge-graceful. The conjecture is still unsettled. In this paper, we give the state of the progress toward this tantalizing conjecture.

Tereza Kovaitova1
1 Department of Mathematics and Statistics University of Minnesota Duluth, MN 55812 Department of Mathematics and Descriptive Geometry Technical University Ostrava, 708 33, Czech Republic
Abstract:

We use a new technique for decomposition of complete graphs with even number of vertices based on \( 2n \)-cyclic blended labeling to show that for every \( k > 1 \) odd, and every \( d \), \( 3 \leq d \leq 2^qk – 1 \), there exists a spanning tree of diameter \( d \) that factorizes \( K_{2^qk} \).

Wensong Chu1, Charles J. Colbourn1, Peter Dukes2
1Department of Computer Science and Engineering Arizona State University Tempe, AZ 85287-5406
2Department of Mathematics University of Toronto Toronto, Ontario CANADA M58 3G3
Abstract:

A constant composition code of length \( n \) over a \( k \)-ary alphabet has the property that the numbers of occurrences of the \( k \) symbols within a codeword is the same for each codeword. These specialize to constant weight codes in the binary case, and permutation codes in the case that each symbol occurs exactly once. Constant composition codes arise in powerline communication and balanced scheduling, and are used in the construction of permutation codes. Using exhaustive and probabilistic clique search, and by applying theorems and constructions in past literature, we generate tables which summarize the best known lower bounds on constant composition codes for (i) \( 3 \leq k \leq 8 \), (ii) \( k = 3 \), \( 9 \leq n \leq 12 \), and (iii) various other interesting parameters with \( n \geq 9 \).

Kimberly A.Lauinger1, Donald L.Kreher1, Rolf Rees2, D.R. Stinson3
1Department of Mathematical Sciences Michigan Technological University Houghton, MI 49931-1295, USA
2Department of Mathematics and Statistics Memorial University of Newfoundland St. John’s, Newfoundland A1C 587, Canada
3School of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1, Canada
Abstract:

In this paper, we develop a computational method for constructing transverse \( t \)-designs. An algorithm is presented that computes the \( G \)-orbits of \( k \)-element subsets transverse to a partition \( \mathcal{H} \), given that an automorphism group \( G \) is provided. We then use this method to investigate transverse Steiner quadruple systems. We also develop recursive constructions for transverse Steiner quadruple systems, and we provide a table of existence results for these designs when the number of points \( v \leq 24 \). Finally, some results on transverse \( t \)-designs with \( t > 3 \) are also presented.

Petr Kovai1
1Department of Mathematics and Statistics University of MN Duluth, Minnesota 55812, USA Department of Mathematics and Descriptive Geometry Technical University Ostrava, 708 33, Czech Republic
Abstract:

A vertex-magic total labeling of a graph \( G(V, E) \) is defined as a one-to-one mapping from \( V \cup E \) to the set of integers \( \{1,2,\ldots,|V| + |E|\} \) with the property that the sum of the label of a vertex and the labels of all edges incident to this vertex is the same constant for all vertices of the graph. A supermagic labeling of a graph \( G(V, E) \) is defined as a one-to-one mapping from \( E \) to the set of integers \( \{1, 2,\ldots,|E|\} \) with the property that the sum of the labels of all edges incident to a vertex is the same constant for all vertices of the graph.

In this paper, we present a technique for constructing vertex-magic total labelings of products of certain vertex-magic total \( r \)-regular graphs \( G \) and certain \( 2_s \)-regular supermagic graphs \( H \). \( H \) has to be decomposable into two \( s \)-regular factors and if \( r \) is even, \( |H| \) has to be odd.

John Martino1, Paula Smith2
1Western Michigan University
2Ohio Dominican University
Abstract:

At each vertex in a Cayley map, the darts emanating from that vertex are labeled by a generating set of a group. This generating set is closed under inverses. Two classes of Cayley maps are balanced and antibalanced maps. For these cases, the distributions of the inverses about the vertex are well understood. For a balanced Cayley map, either all the generators are involutions or each generator is directly opposite across the vertex from its inverse. For an antibalanced Cayley map, there is a line of reflection in the tangent plane of the vertex so that the inverse generator for each dart label is symmetric across that line. An \( e \)-balanced Cayley map is a recent generalization that has received much study, see for example [2, 6, 7, 13]. In this note, we examine the symmetries of the inverse distributions of \( e \)-balanced maps in a manner analogous to those of balanced and antibalanced maps.

Sergey Kitaev1, Toufik Mansour2
1MATEMATIK, CHALMERS TEKNISKA HOGSKOLA OCH GOTEBORGS UNIVERSITET, 412 96 GOTEBORG, SWEDEN
2 DEPARTMENT OF MATHEMATICS, CHALMERS UNIVERSITY OF TECHNOLOGY, 412 96 GOTEBORG, SWEDEN
Abstract:

In [Kit1] Kitaev discussed simultaneous avoidance of two \(3\)-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such \(n\)-permutations are \(2^{n-1}\), the number of involutions in \(S_n\), and \(2^{E_n}\), where \(E_n\) is the \(n\)-th Euler number. In this paper we give recurrence relations for the remaining three essentially different cases.

To complete the descriptions in [Kit3] and [KitMans], we consider avoidance of a pattern of the form \(x-y-z\) (a classical \(3\)-pattern) and beginning or ending with an increasing or decreasing pattern. Moreover, we generalize this problem: we demand that a permutation must avoid a \(3\)-pattern, begin with a certain pattern, and end with a certain pattern simultaneously. We find the number of such permutations in case of avoiding an arbitrary generalized \(3\)-pattern and beginning and ending with increasing or decreasing patterns.

Ligong Wang1, Xueliang Li2, C. Hoede3
1Department of Applied Mathematics, Northwestern Polytechnical University, Xi‘an, Shaanxi, 710072, P. R.China.
2Center for Combinatorics, Nankai University, Tianjin, 360071, P. R. China.
3Faculty of Mathematical Science, University of Twente, P.O.Box 217,7500 AE Enschede, The Netherlands.
Abstract:

A graph \(G\) is called integral or Laplacian integral if all the eigenvalues of the adjacency matrix \(A(G)\) or the Laplacian matrix \(Lap(G) = D(G) – A(G)\) of \(G\) are integers, where \(D(G)\) denotes the diagonal matrix of the vertex degrees of \(G\). Let \(K_{n,n+1} \equiv K_{n+1,n}\) and \(K_{1,p}[(p-1)K_p]\) denote the \((n+1)\)-regular graph with \(4n+2\) vertices and the \(p\)-regular graph with \(p^2 + 1\) vertices, respectively. In this paper, we shall give the spectra and characteristic polynomials of \(K_{n,n+1} \equiv K_{n+1,n}\) and \(K_{1,p}[(p-1)K_p]\) from the theory on matrices. We derive the characteristic polynomials for their complement graphs, their line graphs, the complement graphs of their line graphs, and the line graphs of their complement graphs. We also obtain the numbers of spanning trees for such graphs. When \(p = n^2 + n + 1\), these graphs are not only integral but also Laplacian integral. The discovery of these integral graphs is a new contribution to the search of integral graphs.

G. Sethuraman1, A. Elumalai1
1School of Mathematics Anna University Chennai-600 025 INDIA
Abstract:

Balakrishnan et al. \([1, 2]\) have shown that every graph is a subgraph of a graceful graph and an elegant graph. Also Liu and Zhang \([4]\) have shown that every graph is a subgraph of a harmonious graph. In this paper we prove a generalization of these two results that any given set of graphs \(G_1,G_1,\ldots,G_i\) can be packed into a graceful/harmonious/elegant graph.

Arnold Knopfmacher1, Neville Robbins2
1THE JOHN KNOPFMACHER CENTRE FOR APPLICABLE ANALY- sis AND NUMBER THEORY, UNIVERSITY OF THE WITWATERSRAND, P. O. Wits, 2050 JOHANNESBURG, SOUTH AFRICA,
2MATHEMATICS DEPARTMENT, SAN FRANCISCO StaTE UNIVERSITY, CA 94132, U.S.A.,
Abstract:

We consider compositions or ordered partitions of the natural number n for which the largest (resp. smallest) summand occurs in the first position of the composition.

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;