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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 054
- Pages: 83-98
- Published: 31/08/2005
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 054
- Pages: 67-81
- Published: 31/08/2005
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} \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 054
- Pages: 57-65
- Published: 31/08/2005
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 \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 054
- Pages: 33-56
- Published: 31/08/2005
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 054
- Pages: 21-31
- Published: 31/08/2005
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.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 054
- Pages: 3-20
- Published: 31/08/2005
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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 076
- Pages: 321-350
- Published: 31/07/2005
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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 076
- Pages: 303-319
- Published: 31/07/2005
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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 076
- Pages: 297-301
- Published: 31/07/2005
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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 076
- Pages: 287-295
- Published: 31/07/2005
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.




