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.

J. P. McSorley 1, W. D. Wallis1
1Department of Mathematics, Southern Illinois University Carbondale, IL 62901-4408. USA.
Abstract:

For a vertex \( x \) in a graph \( G \), we define \( \Psi_1(x) \) to be the number of edges in the closed neighborhood of \( x \). Vertex \( x^* \) is a neighborhood champion if \( \Psi_1(x^*) > \Psi_1(x) \) for all \( x \neq x^* \). We also refer to such an \( x^* \) as a unique champion. For \( d \geq 4 \), let \( n_0(1,d) \) be the smallest number such that for every \( n \geq n_0(1,d) \) there exists an \( n \)-vertex \( d \)-regular graph with a unique champion. Our main result is that \( n_0(1,d) \) satisfies \( d+3 \leq n_0(1,d) < 3d+1 \). We also observe that there can be no unique champion vertex when \( d = 3 \).

D.V. Chopra1, Richard M.Low2, R. Dios3
1Department of Mathematics and Statistics Wichita State University Wichita, KS 67260-0033, USA
2Department of Mathematics San Jose State University San Jose, CA 95192, USA
3Department of Mathematics New Jersey Institute of Technology Newark, NJ 07102-1982, USA
Abstract:

In this paper, we consider the non-existence of some bi-level orthogonal arrays (O-arrays) of strength six, with \( m \) constraints (\( 6 \leq m \leq 32 \)), and with index set \( \mu \) (\( 1 \leq \mu \leq 512 \)). The results presented here tend to improve upon the results available in the literature.

P.Mark Kayll1, David Perkins2
1Department of Mathematical Sciences, University of Montana Missoula MT 59812-0864, USA
2Department of Mathematics and Computer Science Houghton College, Houghton NY 14744, USA
Spencer P.Hurd1, Nutan Mishra2, Dinesh G. Sarvate3
1The Citadel, Dept. Math/CS, Charleston, SC, 29409
2Dept. Math. Stastist., Univ. South Alabama, Mobile, AL
3College of Charleston, Dept. Math, Charleston, SC, 29424
Abstract:

We present constructions and results about GDDs with two groups and block size five in which each block has configuration \((s, t)\), that is, in which each block has exactly \(s\) points from one of the two groups and \(t\) points from the other. After some results for a general \(k\), \(s\), and \(t\), we consider the \((2,3)\) case for block size \(5\). We give new necessary conditions for this family of GDDs and give minimal or near-minimal index examples for all group sizes \(n \geq 4\) except for \(n = 24s + 17\).

Patrick Bahls1
1Department of Mathematics University of North Carolina, Asheville, NC 28804
Abstract:

We compute the limiting average connectivity \(\overline{\kappa}\) of the family of \(3\)-regular expander graphs whose members are formed from the finite fields \(\mathbb{Z}_p\), by connecting every \(x \in \mathbb{Z}_p\) with \(x\pm1\) and \(x^{-1}\), all computations performed modulo \(p\). Namely, we show

\[\lim_{p\to\infty} \overline{\kappa}(\mathbb{Z}_p) = 3\]

for primes \(p\). We compare this behavior with an upper bound on the expected value of \(\overline{\kappa}(\mathbb{Z}_n)\) for a more general class \(\{\mathbb{Z}_n\}_{n\in\mathbb{N}}\) of related graphs.

Nick C.Fiala1
1Department of Mathematics St. Cloud State University St. Cloud, MN 56301
Abstract:

An \(\lambda\)-design on \(v\) points is a set of \(v\) subsets (blocks) of a \(v\)-set such that any two distinct blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that all \(\alpha\)-designs can be obtained from symmetric designs by a complementation procedure. In a previous paper, the author established feasibility criteria for the existence of \(\lambda\)-designs with two block sizes in the form of integrality conditions, equations, inequalities, and Diophantine equations involving various parameters of the designs. In that paper, these criteria and a computer were used to prove that the \(\lambda\)-design conjecture is true for all \(\lambda\)-designs with two block sizes with \(\lambda \leq 90\) and \(\lambda \neq 45\). In this paper, we extend these results and prove that the \(\lambda\)-design conjecture is also true for all \(\lambda\)-designs with two block sizes with \(\lambda = 45\) or \(91 \leq \alpha < 150\).

M. Esmaeili1, V. Ravanmehr1
1Department of Mathematical Sciences Isfahan University of Technology 84156-83111, Isfahan, Iran
Abstract:

The binary linear code \(H^\bot_{m,2}\), \(m > 2\), of length \(\binom{m}{2}\) represented by the generator matrix \(H_{m,2}\) consisting of all distinct column strings of length \(m\) and Hamming weight \(2\) is considered. A parity-check matrix \(H^\bot_{m,2}\) is assigned to the code \(H^\bot_{m,2}\). The code \(H_{m,2,3}\), \(m > 3\), of length \(\binom{m}{2} + \binom{m}{3}\) represented by the parity-check matrix \(H_{m,2,3}\) consisting of all distinct column strings of length \(m\) and Hamming weight two or three is also considered. It is shown that \(H^\bot_{m,2}\) and \(H_{m,2,3}\) are optimal stopping redundancy codes, that is for each of these codes the stopping distance of the associated parity-check matrix is equal to the minimum Hamming distance of the code, and the rows of the parity-check matrix are linearly independent. Explicit formulas determining the number of stopping sets of arbitrary size for these codes are given.

Ying Xu1, Jixiang Meng1
1College of Mathematics and Systems Science, Xinjiang University, Urumdai, Xinjiang 830046, P. R. China
Abstract:

For a finite group \(G\) and subsets \(T_1, T_2\) of \(G\), the Bi-Cayley digraph \(D = (V(D), E(D)) = D(G, T_1, T_2)\) of \(G\) with respect to \(T_1\) and \(T_2\) is defined as the bipartite digraph with vertex set \(V(D) = G \times \{0, 1\}\), and for \(g_1, g_2 \in G\), \(((g_1, 0), (g_2, 1)) \in E(D)\) if and only if \(g_2 = t_1 g_1\) for some \(t_1 \in T_1\), and \(((g_1, 1), (g_2, 0)) \in E(D)\) if and only if \(g_1 = t_2 g_2\) for some \(t_2 \in T_2\). If \(|T_1| = |T_2| = k\), then \(D\) is \(k\)-regular. In this paper, the spectra of Bi-Circulant digraphs are determined. In addition, some asymptotic enumeration theorems for the number of directed spanning trees in Bi-Circulant digraphs are presented.

Jianchu Zeng1, Yanpei Liu1
1DEPARTMENT OF MATHEMATICS, BEIJING JIAOTONG UNIVERSITY BEIJING 100044, P. R, CHINA
Abstract:

The genus of a graph \(G\), denoted by \(\gamma(G)\), is the minimum genus of an orientable surface in which the graph can be embedded. In the paper, we use the Joint Tree Model to immerse a graph on the plane and obtain an associated polygon of the graph. Along the way, we construct a genus embedding of the edge disjoint union of \(K\) and \(H\), and solve Michael Stiebitz’s proposed conjecture: Let \(G\) be the edge disjoint union of a complete graph \(K\) and an arbitrary graph \(H\). Let \(H’\) be the graph obtained from \(H\) by contracting the set \(V(X)\) to a single vertex. Then

\[\gamma(K) + \gamma(H’) \leq \gamma(G).\]

David R.Berman1, Malcolm Greig2, Douglas D.Smith3
1Computer Science Department University of North Carolina Wilmington
2Greig Consulting, 317-130 East 11th Street, North Vancouver, B.C., Canada
3Mathematics and Statistics Department University of North Carolina Wilmington
Abstract:

We investigate brother avoiding round robin doubles tournaments and construct several infinite families. We show that there is a BARRDT(\(x\)) that is not a SAMDRR(\(n\)) for all \(n > 4\).

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;