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.

Jianqin Zhou1,2, Xirong Xu3
1Telecommunication School Hangzhou Dianzi University, Hangzhou 310018, China
2Computer Science School Anhui University of Technology, Ma’anshan 243002, China
3Department of Computer Science Dalian University of Technology, Dalian 116024, China
Abstract:

Double-loop networks have been widely studied as architecture for local area networks. A double-loop network \(G(N;s_1,s_2)\) is a digraph with \(N\) vertices \(0,1,\ldots,N-1\) and \(2N\) edges of two types:

\(s_1-edge\): \(i \rightarrow i+s_1 \pmod{N}\); \(i=0,1,\ldots,N-1\).

\(s_2-edge\): \(i \rightarrow i+s_2 \pmod{N}\); \(i=0,1,\ldots,N-1\).

for some fixed steps \(1 \leq s_1 < s_2 < N\) with \(\gcd(N,s_1,s_2) = 1\). Let \(D(N;s_1,s_2)\) be the diameter of \(G\) and let us define \(D(N) = \min\{D(N;s_1,s_2) | 1 \leq s_1 < s_2 < N \text{ and } gcd(N,s_1,s_2) = 1\}\), and \(D_1(N) = \min\{D(N;1,s) | 1 < s < N\}\). If \(N\) is a positive integer and \(D(N) < D_1(N)\), then \(N\) is called a non-unit step integer or a nus integer. Xu and Aguild et al. gave some infinite families of 0-tight nus integers with \(D_1(N) – D(N) \geq 1\). In this work, we give a method for finding infinite families of nus integers. As application examples, we give one infinite family of 0-tight nus integers with \(D_1(N) – D(N) \geq 5\), one infinite family of 2-tight nus integers with \(D_1(N) – D(N) \geq 1\) and one infinite family of 3-tight nus integers with \(D_1(N) – D(N) \geq 1\).

Wenchang Chu1, Xiaoxia Wang2
1angzhou Normal University Institute of Combinatorial Mathematics Hangzhou 310096, P. R. China
2Shanghai University Department of Mathematics Shanghai 200444, P. R. China
Abstract:

Ramanujan’s \(\mathop{_1\psi_1}\)-summation formula is one of the fundamental identities in basic hypergeometric series. We review proofs of this identity and clarify its connections with other basic hypergeometric series transformations and formulae. In particular, we shall put our main emphasis on methods that can be used not only to provide deeper insight into Ramanujan’s \(\mathop{_1\psi_1}\)-summation formula, but also to derive new transformations and identities for basic hypergeometric series.

Abstract:

A diagonalised lattice is a two dimensional grid, where we add exactly one arbitrary diagonal in each square, and color each vertex black or white.We show that for every diagonalised lattice there is a walk from the left to the right, using only black vertices, if and only if there is no walk from the top to the bottom, using only white vertices.

Ian Anderson1, D.A. Preece2,3
1Department of Mathematics, University of Glasgow, University Gardens, Glasgow G12 8QW, UK
2School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK
3Institute of Mathematics, Statistics and Actuarial Science, Cornwallis Building, University of Kent, Canterbury, Kent CT2 7NF, UK
Abstract:

A terrace for \(\mathbb{Z}_m\) is an arrangement \((a_1, a_2, \ldots, a_m)\) of the \(m\) elements of \(\mathbb{Z}_m\) such that the sets of differences \(a_{i+1} – a_i\) and \(a_i – a_{i+1}\) (\(i = 1, 2, \ldots, m-1\)) between them contain each element of \(\mathbb{Z}_m \setminus \{0\}\) exactly twice. For \(m\) odd, many procedures are available for constructing power-sequence terraces for \(\mathbb{Z}_m\); each such terrace may be partitioned into segments one of which contains merely the zero element of \(\mathbb{Z}_m\) whereas each other segment is either (a) a sequence of successive powers of a non-zero element of \(\mathbb{Z}_m\) or (b) such a sequence multiplied throughout by a constant. For \(n\) an odd prime power satisfying \(n \equiv 1\) or \(3 \pmod{8}\), this idea has previously been extended by using power-sequences in \(\mathbb{Z}_n\) to produce some \(\mathbb{Z}_m\) terraces \((a_1, a_2, \ldots, a_m)\) where \(m = n+1 = 2^\mu\), with \(a_{i+1} – a_i = -(a_{i+1+\mu} – a_{i+\mu})\) for all \(i \in [1, \mu-1]\). Each of these “da capo directed terraces” consists of a sequence of segments, one containing just the element \(0\) and another just containing the element \(n\), the remaining segments each being of type (a) or (b) above with each of its distinct entries \(z\) from \(\mathbb{Z}_n \setminus \{0\}\) evaluated so that \(1 \leq x \leq n-1\). Now, for many odd prime powers \(n\) satisfying \(n \equiv 1 \pmod{4}\), we similarly produce narcissistic terraces for \(\mathbb{Z}_{n+1}\); these have \(a_{i+1} – a_i = a_{m-i+1} – a_{m-i}\) for all \(i \in [1, \mu-1]\).

Edward Dobson1
1Department of Mathematics and Statistics Mississippi State University PO Drawer MA Mississippi State, MS 39762
Abstract:

We determine the full Sylow \(p\)-subgroup of the automorphism group of transitive \(k\)-ary relational structures of order \(p^2\), \(p\) a prime. We then find the full automorphism group of transitive ternary relational structures of order \(p^2\), for those values of \(p\) for which \({A_p}\) is the only doubly-transitive nonabelian simple group of degree \(p\). Finally, we determine optimal necessary and sufficient conditions for two Cayley \(k\)-ary relational structures of order \(p^2\), \(k < p\), to be isomorphic.

Fengxia Liu1, Jixiang Meng1
1College of Mathematics and Systems Science, Xinjiang University, Urumqi, Xinjiang 880046, P.R. China
Abstract:

Let \(G\) be a finite group, \(S\) (possibly, contains the identity element) be a subset of \(G\). The Bi-Cayley graph \(\text{BC}(G, S)\) is a bipartite graph with vertex set \(G \times \{0,1\}\) and edge set \(\{\{(g,0), (gs,1)\}, g \in G, s \in S\}\). A graph \(X\) is said to be super-edge-connected if every minimum edge cut of \(X\) is a set of edges incident with some vertex. The restricted edge connectivity \(\lambda'(X)\) of \(X\) is the minimum number of edges whose removal disconnects \(X\) into nontrivial components. A \(k\)-regular graph \(X\) is said to be optimally super-edge-connected if \(X\) is super-edge-connected and its restricted edge connectivity attains the maximum \(2k-2\). In this paper, we show that all connected Bi-Cayley graphs, except even cycles, are optimally super-edge-connected.

Neil P.Carnes1, Anne Dye1
1Department of Mathematics, Computer Science, and Statistics McNeese State University Lake Charles, LA 70609-2340
Abstract:

A transitive triple, \((a, b, c)\), is defined to be the set \(\{(a, b), (b, c), (a, c)\}\) of ordered pairs. A directed triple system of order \(v\), \(DTS(v)\), is a pair \((D, \beta)\), where \(D\) is a set of \(v\) points and \(\beta\) is a collection of transitive triples of pairwise distinct points of \(D\) such that any ordered pair of distinct points of \(D\) is contained in precisely one transitive triple of \(\beta\). An antiautomorphism of a directed triple system, \((D, \beta)\), is a permutation of \(D\) which maps \(\beta\) to \(\beta^{-1}\), where \(\beta^{-1} = \{(c, b, a) | (a, b, c) \in \beta\}\). In this paper, we give necessary and sufficient conditions for the existence of a directed triple system of order \(v\) admitting an antiautomorphism consisting of two cycles of lengths \(M\) and \(2M\), and one fixed point.

Hung-Chih Lee1
1Department of Information Technology Ling Tung University Taichung 40852, Taiwan
Abstract:

A \(k\)-circuit is a directed cycle of length \(k\). In this paper, we completely solve the problem of finding maximum packings and minimum coverings of \(\lambda\)-fold complete bipartite symmetric digraphs with \(6\)-circuits.

Xianghong Xu1, Weijun Liu1
1School of Sciences, Nantong University, Nantong, Jiangsu, 226007, P. R. China
Abstract:

Until now, all known simple \(t-(v, k, \lambda)\) designs with \(t \geq 6\) have \(\lambda \geq 4\). On the other hand, P. J. Cameron and C. E. Praeger showed that there are no flag-transitive simple \(7-(v, k, \lambda)\) designs. In the present paper, we considered the flag-transitive simple \(6-(v, k, \lambda)\) designs and proved that there are no non-trivial flag-transitive simple \(6-(v, k, \lambda)\) designs with \(\lambda \leq 5\).

John Mitchem1, Randolph L.Schmidt2
1Mathematics Department San Jose State University, San Jose, CA 95192
2RSE Consulting, Mountain View, CA 94043
Abstract:

In \(1972\), Erdős, Faber, and Lovász made the now famous conjecture: If a graph \(G\) consists of \(n\) copies of the complete graph \(K_n\), such that any two copies have at most one common vertex (such graphs are called EFL graphs), then \(G\) is \(n\)-colorable. In this paper, we show that the conjecture is true for two different classes of EFL graphs. Furthermore, a new shorter proof of the conjecture is given for a third class of EFL graphs.

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;