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.

Luigia Berardi1, Franco Eugeni1
1Dipartimento di Ingegneria Elettrica L’ Aquila (ITA)
Abstract:

Blocking sets in little and large Mathieu designs, have all been characterized except the case \(S(5, 8, 24)\). The aim of this paper is to give the complete classification of blocking sets in this remaining case.

H.J. Veldman1
1 Faculty of Applied Mathematics University of Twente 7500 AE Enschede THE NETHERLANDS
Abstract:

For a graph \(G\), define \(\phi(G) = \min \{\max \{d(u), d(v)\} | d(u,v) = 2\}\) if \(G\) contains two vertices at distance 2, and \(\phi(G) = \infty\) otherwise. Fan proved that every 2-connected graph on \(n\) vertices with \(\phi(G) > \frac{1}{2}n\) is hamiltonian. Short proofs of this result and a number of analogues, some known, some new, are presented. Also, it is shown that if \(G\) is 2-connected, \(\phi(G) \geq \frac{1}{2}(n-i)\) and \(G – \{v \in V(G) | d(v) \geq \frac{1}{2} (n-i)\}\) has at least three components with more than \(i\) vertices, then \(G\) is hamiltonian (\(i \geq1\)).

Antoine C. Lobstein 1
1Centre National de la Recherche Scientifique, URA 251, Télécom Paris, Département Informatique, 46 rue Barrault, 75634 Paris Cedex 13, France.
Abstract:

We state here that, for modulus \(m\) odd and less than \(2^{29}+2^{27} – 1\), no (nontrivial) perfect binary arithmetic code, correcting two errors or more, exists (this is to be taken with respect to the Garcia-Rao modular distance). In particular, in the case \(m = 2^n \pm 1\), which is most frequently studied, no such code exists for \(m < 2^{33} – 1\).

D. G. Sarvate1
1 Department of Mathematics College of Charleston Charleston, South Carolina 29424 U.S.A.
Abstract:

Constructions of partially balanced incomplete block designs with three and four associate classes are given. The constructions use \(\epsilon\)-designs for \(t=6\) and \(t=8\).

Ahmed Assaf 1
1Department of Algebra, Combinatorics and Analysis Auburn University
Abstract:

Let \(X\) be a finite set of order \(mn\), and assume that the points of \(X\) are arranged in an array of size \(m \times n\). The columns of the array will be called groups.
In this paper we consider a new type of group divisible designs called modified group divisible designs in which each \(\{x,y\} \subseteq X\) such that \(x\) and \(y\) are neither in the same group nor in the same row occurs \(\lambda\) times. This problem was motivated by the problem of resolvable group divisible designs with \(k = 3\), \(\lambda = 2\) [1] , and other constructions of designs.

Zhang Xuebin1
1Department of Mathematics Suzhou University, Suzhou People’s Republic of China
Abstract:

FE. Bennett has proved that a \((v, 4, 1)\)-RPMD exists for every positive integer \(v \equiv 1 \pmod{4}\) with the possible exception of \(v = 33, 57, 93\) and \(133\). In this paper, we shall first introduce the concept of an incomplete PMD and use it to establish some construction methods for Mendelsohn designs; then we shall give the following results: (1) a \((v, 4, 1)\)-PMD exists for every positive integer \(v \equiv 0 \pmod{4}\) with the exception of \(v = 4\) and the possible exception of \(v = 8, 12\);(2) a \((v, 4, 1)\)-PMD exists if \(v = 57, 93\) or \(133\).

Cao Hui-Zhong1
1Department of Mathematics Shandong University Jinan, Shandong China
Abstract:

Let \(f(n)\) denote the number of essentially different factorizations of \(n\). In this paper, we prove that for every odd number \( > 1\), we have \(f(n) \leq c\frac{n}{\log n},\) where \(c\) is a positive constant.

Zbigniew Lonc1
1Institute of Mathematics Warsaw University of Technology Warsaw, Poland
Abstract:

A partition of the edge set of a hypergraph \(H\) into subsets inducing hypergraphs \(H_1,\ldots,H_r\) is said to be a \({decomposition}\) of \(H\) into \(H_1,\ldots,H_r\). A uniform hypergraph \(F = (\bigcup \mathcal{F}, \mathcal{F})\) is a \(\Delta\)-\({system}\) if there is a set \(K \subseteq V(F)\), called the \({kernel}\) of \(F\), such that \(A \cap B = K\) for every \(A, B \in \mathcal{F}\), \(A \neq B\). A disjoint union of \(\Delta\)-systems whose kernels have the same cardinality is said to be a \(constellation\). In the paper, we find sufficient conditions for the existence of a decomposition of a hypergraph \(H\) into:
a) \(\Delta\)-systems having almost equal sizes and kernels of the same cardinality,
b) isomorphic copies of constellations such that the sizes of their components are relatively prime.

In both cases, the sufficient conditions are satisfied by a wide class of hypergraphs \(H\).

Wayne Goddard1
1Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139
Abstract:

The binding number of a graph \(G\) is defined to be the minimum of \(|N(S)|/|S|\) taken over all nonempty \(S \subseteq V(G)\) such that \(N(S) \neq V(G)\). In this paper, another look is taken at the basic properties of the binding number. Several bounds are established, including ones linking the binding number of a tree to the “distribution” of its end-vertices. Further, it is established that under some simple conditions, \(K_{1,3}\)-free graphs have binding number equal to \((p(G) – 1)/(p(G) – \delta(G))\) and applications of this are considered.

Bert L.Hartnell1, Neville Jeans2, William Kocay2
1St. Mary’s University Halifax, Canada,
2University of Manitoba Winnipeg, Canada
Abstract:

Strongly regular graphs are graphs in which every adjacent pair of vertices share \(\lambda\) common neighbours and every non-adjacent pair share \(\mu\) common neighbours. We are interested in strongly regular graphs with \(\lambda = \mu = k\) such that every such set of \(k\) vertices common to any pair always induces a subgraph with a constant number \(x\) of edges. The Friendship Theorem proves that there are no such graphs when \(\lambda = \mu = 1\). We derive constraints which such graphs must satisfy in general, when \(\lambda = \mu > 1\), and \(x \geq 0\), and we find the set of all parameters satisfying the constraints. The result is an infinite, but sparse, collection of parameter sets. The smallest parameter set for which a graph may exist has \(4896\) vertices, with \(k = 1870\).

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;