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.

Miho Kimura 1, Sanpei Kageyama1
1Department of Mathematics, Graduate School of Education Hiroshima University, Higashi-Hiroshima 739-8524, Japan
Abstract:

Large sets of balanced incomplete block (\(BIB\)) designs and resolvable \(BIB\) designs are discussed. Some recursive constructions of such large sets are given. Some existence results, in particular for practical \(k\), are reviewed.

Hendrik Van Maldeghem1, Valerie Ver Gucht2
1Dopartinent: of Pure Mathematics and Computer Algebra Ghent University aalglann 2. 9000 Gent BELGIUM
2Departinent of Applied Mathematics, Biometrics aud Process Control Ghent. University Coupure Links 653. 9000 Gent BELGIUM
Abstract:

We consider point-line geometries having three points on every line, having three lines through every point (\(bi\)-\(slim\; geometries\)), and containing triangles. We give some (new) constructions and we prove that every flag-transitive such geometry either belongs to a certain infinite class described by Coxeter a long time ago, or is one of three well-defined sporadic ones, namely, The Möbius-Kantor geometry on \(8\) points, The Desargues geometry on \(10\) points,A unique infinite example related to the tiling of the real Euclidean plane in regular hexagons.We also classify the possible groups.

P. Katerinis1
1Athens University of Economics Department of Informatics 76 Patission Str., Athens 10434, Greece
Abstract:

Let \(G\) be a simple graph such that \(\delta(G) \geq \lfloor\frac{|V(G)|}{2}\rfloor + k\), where \(k\) is a non-negative integer, and let \(f: V(G) \to \mathbb{Z}^+\) be a function having the following properties (i)\(\frac{d_G(x)}{2}-\frac{k+1}{2}\leq f(x)\leq \frac{d_G(x)}{2}+\frac{k+1}{2}\) for every \(x \in V(G)\), (ii)\(\sum\limits_{x\in V(G)}f(x)=|E(G)|\). Then \(G\) has an orientation \(D\) such that \(d^+_D(x) = f(x)\), for every \(x \in V(G)\).

Ji Young Choi1, Jonathan D.H.Smith2
1DEPARTMENT OF MATHEMATICS, SHIPPENSBURG UNIVERSITY, SHIPPENSBURG, PA 17257, USA
2DEPARTMENT OF MATHEMATICS, Lowa STATE UNiversiTY, Ames, IA 50011, USA
Abstract:

The so-called multi-restricted numbers generalize and extend the role of Stirling numbers and Bessel numbers in various problems of combinatorial enumeration. Multi-restricted numbers of the second kind count set partitions with a given number of parts, none of whose cardinalities may exceed a fixed threshold or “restriction”. The numbers are shown to satisfy a three-term recurrence relation. Both analytic and combinatorial proofs for this relation are presented. Multi-restricted numbers of both the first and second kinds provide connections between the orbit decompositions of subsets of powers of a finite group permutation representation, in which the number of occurrences of elements is restricted. An exponential generating function for the number of orbits on such restricted powers is given in terms of powers of partial sums of the exponential function.

Stephen Guattery1, Gary Haggard1, Ronald C.Read2
1Bucknell University
2University of Waterloo
Abstract:

A class of graphs called generalized ladder graphs is defined. A sufficient condition for pairs of these graphs to be chromatically equivalent is proven. In addition, a formula for the chromatic polynomial of a graph of this type is proven. Finally, the chromatic polynomials of special cases of these graphs are explicitly computed.

Haruko Okamura1
1Dept. of Information Science and Systems Engineering Konan University Okamoto Kobe 658-8501, Japan
Abstract:

Let \(k \geq 3\) be odd and \(G = (V(G), E(G))\) be a \(k\)-edge-connected graph. For \(X \subseteq V(G)\), \(e(X)\) denotes the number of edges between \(X\) and \(V(G) – X\). We here prove that if \(\{s_i, t_i\} \subseteq X_i \subseteq V(G)\), \(i = 1, 2\), \(X_1 \cap X_2 = \emptyset\), \(e(X_1) \leq 2k-2\) and \(e(X_2) < 2k-1\), then there exist paths \(P_1\) and \(P_2\) such that \(P_i\) joins \(s_i\) and \(t_i\), \(V(P_i) \subseteq X_i\) (\(i = 1, 2\)) and \(G – E(P_1 \cup P_2)\) is \((k-2)\)-edge-connected. And in fact, we give a generalization of this result and some other results about paths not containing given edges.

M. Esmaeili1, M.R. Yazdani2, T.A. Gulliver3
1Department of Mathematical Sciences Isfahan University of Technology, Isfahan, Iran
2Dept. of Systems and Computer Engineering Carleton University, Ottawa, Canada
3Dept. of Electrical and Computer Engineering University of Victoria, P.O. Box 3055, STN CSC Victoria, B.C., Canada V8W 3P6
Abstract:

Optimal binary linear codes of length \(18\) containing the \([6, 5, 2]\otimes[ 3, 1, 3]\) product code are presented. It is shown that these are \([18, 9, 5]\) and \([18, 8, 6]\) codes. The soft-decision maximum-likelihood decoding complexity of these codes is determined. From this point of view, these codes are better than the \([18, 9, 6]\) code.

Samina Boxwala1, N.B. Limaye2
1Department of Mathematics, N. Wadia College, Pune,411001.
2Department of Mathematics, University of Mumbai, Vidyanagari, Mumbai 400098, INDIA
Abstract:

An elongated ply \( T(n; t^{(1)}, t^{(2)}, \ldots, t^{(n)}) \) is a snake of \( n \) number of plys \( P_{t(i)} (u_i, u_{i+1}) \) where any two adjacent plys \( P_{t(i)} \) and \( P_{t(i+1)} \) have only the vertex \( u_{i+1} \) in common. That means the block cut vertex graph of \( T_n \) is thus a path of length \( n – 1 \). In this paper, the cordiality of the Elongated Ply \( T_n \) is investigated.

Wayne Goddard1, Sandra M.Hedetniemi1, Stephen T.Hedetniemi1
1Department of Computer Science, Clemson University Clemson SC 29634, USA
Abstract:

Consider placing a guard on each vertex of a dominating set \( S_0 \) of a graph. If for every vertex \( v \notin S_0 \), there is a corresponding guard at an adjacent vertex \( u \) for which the resulting set \( S_1 = S_0 – \{u\} \cup \{v\} \) is dominating, then we say that \( S_0 \) is \( 1 \)-secure. It is eternally \( 1 \)-secure if for any sequence \( v_1, v_2, \ldots, v_k \) of vertices, there exists a sequence of guards \( u_1, u_2, \ldots, u_k \) with \( u_i \in S_{i-1} \) and \( u_i \) equal to or adjacent to \( v_i \), such that each set \( S_i = S_{i-1} – \{u_i\} \cup \{v_i\} \) is dominating. We investigate the minimum cardinality of an eternally secure set. In particular, we refute a conjecture of Burger et al. We also investigate eternal \( m \)-security, in which all guards can move simultaneously.

Richard Bean1
1Institute for Studies in Theoretical Physics and Mathematics Department of Mathematics PO Box 19395-5746 Tehran, I.R. Iran
Abstract:

In 1990, Kolesova, Lam, and Thiel determined the 283,657 main classes of Latin squares of order 8. Using techniques to determine relevant Latin trades and integer programming, we examine representatives of each of these main classes and determine that none can contain a uniquely completable set of size less than 16. In three of these main classes, the use of trades which contain less than or equal to three rows, columns, or elements does not suffice to determine this fact. We closely examine properties of representatives of these three main classes. Writing the main result in Nelder’s notation for critical sets, we prove that \( \text{scs}(8) = 16 \).

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;