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 059
- Pages: 119-129
- Published: 30/11/2006
Let \( G \) be a \( (p,q) \)-graph in which the edges are labeled \( 1, 2, 3, \ldots, q \). The vertex sum for a vertex \( v \) is the sum of the labels of the incident edges at \( v \). If \( G \) can be labeled so that the vertex sums are distinct, mod \( p \), then \( G \) is said to be edge-graceful. If the edges of \( G \) can be labeled \( 1, 2, 3, \ldots, q \) so that the vertex sums are constant, mod \( p \), then \( G \) is said to be edge-magic. It is conjectured by Lee [9] that any connected simple \( (p,q) \)-graph with \( q(q+1) \equiv p(p-1)/2 \pmod{p} \) vertices is edge-graceful. We show that the conjecture is true for maximal outerplanar graphs. We also completely determine the edge-magic maximal outerplanar graphs.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 059
- Pages: 101-118
- Published: 30/11/2006
We enumerate the self-orthogonal Latin squares of orders \(1\) through \(9\) and discuss the nature of the isomorphism classes of each order. Furthermore, we consider the possibility of enlarging sets of self-orthogonal Latin squares to produce complete sets.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 059
- Pages: 89-99
- Published: 30/11/2006
A vertex-magic total labeling on a graph with \( v \) vertices and \( e \) edges is a one-to-one map taking the vertices and edges onto the integers \( 1, 2, \ldots, v+e \) with the property that the sum of the label on a vertex and the labels of its incident edges is constant, independent of the choice of vertex. We give vertex-magic total labelings for several classes of regular graphs. The paper concludes with several conjectures and open problems in the area.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 059
- Pages: 33-87
- Published: 30/11/2006
In this paper, we complete the classification of optimal binary linear self-orthogonal codes up to length 25. Optimal self-orthogonal codes are also classified for parameters up to length 40 and dimension 10. The results were obtained via two independent computer searches.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 059
- Pages: 17-32
- Published: 30/11/2006
In this paper we examine the classical Williamson construction for Hadamard matrices, from the point of view of a striking analogy with isomorphisms of division algebras. By interpreting the 4 Williamson array as a matrix arising from the real quaternion division algebra, we construct Williamson arrays with 8 matrices, based on the real octonion division algebra. Using a Computational Algebra formalism we perform exhaustive searches for even-order 4-Williamson matrices up to 18 and odd- and even-order 8-Williamson matrices up to 9 and partial searches for even-order 4-Williamson matrices up to 22 and odd- and even-order 8-Williamson matrices for orders 10 — 13. Using Magma, we conduct searches for inequivalent Hadamard matrices within all the sets of matrices obtained by exhaustive and partial searches. In particular, we establish constructively ten new lower bounds for the number of inequivalent, Hadamard matrices of the consecutive orders 72, 76, 80, 84, 88, 92, 96, 100, 104 and 108.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 059
- Pages: 3-16
- Published: 30/11/2006
This article continues the study of a class of non-terminating expansions of sin\( (m\alpha) \) (even \(m \geq 2 \)) which in each case possesses embedded Catalan numbers. A known series form of the sine function (said to be associated with Euler) is taken here as our basic representation, the coefficient of the general term being developed analytically in an interesting fashion and shown to be dependent on the Catalan sequence in the manner expected.
The work, which has a historical backdrop to it, is discussed in the context of prior results by the author and others.
- Research article
- Full Text
- Ars Combinatoria
- Volume 081
- Pages: 369-379
- Published: 31/10/2006
A connected graph is said to be super edge-connected if every minimum edge-cut isolates a vertex. The restricted edge-connectivity \(\lambda’\) of a connected graph is the minimum number of edges whose deletion results in a disconnected graph such that each connected component has at least two vertices. A graph \(G\) is called \(\lambda’\)-optimal if \(\lambda'(G) = \min\{d_G(u)+d_G(v)-2: uv \text{ is an edge in } G\}\). This paper proves that for any \(d\) and \(n\) with \(d \geq 2\) and \(n\geq 1\) the Kautz undirected graph \(UK(d, 1)\) is \(\lambda’\)-optimal except \(UK(2,1)\) and \(UK(2,2)\) and, hence, is super edge-connected except \(UK(2, 2)\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 081
- Pages: 359-367
- Published: 31/10/2006
In a \((k, d)\)-relaxed coloring game, two players, Alice and Bob, take turns coloring the vertices of a graph \(G\) with colors from a set \(C\) of \(k\) colors. A color \(c\) is legal for an uncolored vertex (at a certain step) means that after coloring \(x\) with color \(i\), the subgraph induced by vertices of color \(i\) has maximum degree at most \(d\). Each player can only color a vertex with a legal color. Alice’s goal is to have all the vertices colored, and Bob’s goal is the opposite: to have an uncolored vertex without legal color. The \(d\)-relaxed game chromatic number of a graph \(G\), denoted by \(\chi^{(d)}_g(G)\) is the least number \(k\) so that when playing the \((k,d)\)-relaxed coloring game on \(G\), Alice has a winning strategy. This paper proves that if \(G\) is an outer planar graph, then \(\chi^{(d)}_g(G) \leq 7 – d\) for \(d = 0, 1, 2, 3, 4\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 081
- Pages: 343-358
- Published: 31/10/2006
A graph \(G\) is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let \(X\) be a 2-stratified graph with one fixed blue vertex \(v\) specified. We say that \(X\) is rooted at \(v\). The \(X\)-domination number of a graph \(G\) is the minimum number of red vertices of \(G\) in a red-blue coloring of the vertices of \(G\) such that every blue vertex \(uv\) of \(G\) belongs to a copy of \(X\) rooted at \(v\). In this paper we investigate the \(X\)-domination number of prisms when \(X\) is a 2-stratified 4-cycle rooted at a blue vertex.
- Research article
- Full Text
- Ars Combinatoria
- Volume 081
- Pages: 325-342
- Published: 31/10/2006
The maximum possible volume of a simple, non-Steiner \((v, 3, 2)\) trade was determined for all \(v\) by Khosrovshahi and Torabi (Ars Combinatoria \(51 (1999), 211-223)\); except that in the case \(v \equiv 5\) (mod 6), \(v \geq 23\), they were only able to provide an upper bound on the volume. In this paper we construct trades with volume equal to that bound for all \(v \equiv 5\) (mod 6), thus completing the problem.




