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.

Zhou Bo1
1 Department of Mathematics South China Normal University Guangzhou 510631 P.R. China
Abstract:

We provide upper estimates on the weak exponent of indecomposability of an irreducible Boolean matrix.

Masakazu Nihei1
1Fujishiro High School Fujishiro, Ibaraki, 300-1537 Japan
Abstract:

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min\left\{\frac{|S|}{\omega(G-S)} \mid S \subseteq V(G), \omega(G-S) \geq 2\right\},\]

where \(\omega(G-S)\) is the number of components of \(G-S\). We also define \(t(K_n) = +\infty\) for every \(n\).

The middle graph \(M(G)\) of a graph \(G\) is the graph obtained from \(G\) by inserting a new vertex into every edge of \(G\) and by joining by edges those pairs of these new vertices which lie on adjacent edges of \(G\).

In this article, we give the toughness of the middle graph of a graph, and using this result we also give a sufficient condition for the middle graph to have a \(k\)-factor.

Malcolm Greig1
1Greig Consulting, 207-170 East Fifth Street, North Vancouver, B.C., Canada, V7L 4L4
Abstract:

This paper gives constructions of balanced incomplete block designs and group divisible designs with \(k = 7, 8,\) or \(9\), and \(\lambda = 1\). The first objective is to give constructions for all possible cases with the exception of \(40, 78,\) and \(157\) values of \(v\). Many of these initial exceptions have now been removed by Abel. In an update section, more are removed; group divisible designs with groups of size \(k(k-1)\) are constructed for \(k = 7\) and \(8\) with \(124\) and \(87\) exceptions; it is also established that \(v \geq 294469\) and \(v \equiv 7\) mod \(42\) suffices for the existence of a resolvable balanced incomplete block design with \(k = 7\). Group divisible designs with group size \(k\) and resolvable designs are constructed.

Mirka Miller1, Martin Baca2, Yuqing Lin3
1Department of Computer Science and Software Engineering The University of Newcastle, NSW 2308, Australia
2 Department of Mathematics Technical University, Kosice, Slovakia
3 Department of Computer Science and Software Engineering The University of Newcastle, NSW 2308, Australia
Abstract:

A connected graph \(G = (V, E)\) is \((a, d)\)-antimagic if there exist positive integers \(a, d\) and a bijection \(g: E \to \{1, 2, \ldots, |E|\}\) such that the induced mapping
\[f_g = \Sigma\{g(u,v): (u, v) \in E(G)\}\, \text{is injective and}\]
\[f_g(V) = \{a, a+d, a+2d, \ldots, a+(|V|-1)d\}.\]
In this paper, we prove two conjectures of Baca concerning \((a, d)\)-antimagic labelings of antiprisms

Chen Kejun1,2
1 Department of Mathematics, Suzhou University Suzhou 215006, China
2Department of Mathematics, Yancheng Teachers College, Jiangsu 224002, China
Abstract:

Some special sum graphs and difference graphs, based on abelian groups, are discussed. In addition to Li’s result on character sum estimates, Weil’s character sum estimates are also used to show that these are indeed Ramanujan graphs.

Peter Adams1, A. Khodkart1
1 Centre for Discrete Mathematics and Computing Department of Mathematics The University of Queensland Queensland 4072 Australia
Abstract:

A critical set in a Latin square of order \(n\) is a set of entries in a Latin square which can be embedded in precisely one Latin square of order \(n\). Also, if any element of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order \(n\). A smallest critical set in a Latin square is a critical set of minimum cardinality. In this paper we find smallest critical sets for all the Latin squares of orders six and seven. We also find smallest critical sets of orders six and seven which are also weak critical sets. In particular, we find a weak critical set of size twelve for the dihedral group of order six.

Yejing Wang1, Reihaneh Safavi-Naini1, Dingyi Pei2
1School of IT and CS, University of Wollongong, Northfields Ave., Wollongong 2522, Australia
2Graduate School at Beijing of USTC, Beijing 100039, China
Abstract:

We study combinatorial structure of \(\ell\)-optimal \(A^2\)-codes that offer the best protection for spoofing of order up to \(\ell\) and require the least number of keys for the transmitter and the receiver. We prove that for such codes the transmitter’s encoding matrix is a strong partially balanced resolvable design, and the receiver’s verification matrix corresponds to an \(\alpha\)-resolvable design with special properties.

B. Du1
1Department of Mathematics Suzhou University Suzhou 215006 China (PRC)
Abstract:

It is proved in this paper that for any integer \(n \geq 136\), a SODLS(\(v, n\)) (self-orthogonal diagonal Latin square with missing subsquare) exists if and only if \(v \geq 3n+2\) and \(v-n\) even.

G.B. Khosrovshahi1,2, H.R. Maimani3, R. Torabi4
1 Department of Mathematics, University of Tehran.
2 Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran
3 Institute for Studies in Theoretical Physics and Mathematics (IPM), and Department of Mathematics, Shahid Rajaee University, Tehran, Iran
4Department of Mathematics, University of Tehran, and Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran
Abstract:

Employing trading signed design algorithm, we construct an automorphism-free \(4\)-\((15, 5, 5)\) design.

N.E. Clarke1, W.D. Garraway1, C.A. Hickman1, R.J. Nowakowski1
1 Department of Math. & Stats. Dalhousie University, Halifax, NS B3H 3J5, Canada.
Abstract:

Consider those graphs \(G\) of size \(2n\) that have an eigenvalue \(\lambda\) of multiplicity \(n\) and where the edges between the star set and its complement is a matching. We show that \(\lambda\) must be either \(0\) or \(1\) and completely characterize the corresponding 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;