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.

Gary Chartrand1, Ping Zhang1
1 Western Michigan University
Abstract:

For two vertices \(u\)  and \(v\) of a connected graph \(G\) , the set \(H(u,v)\) consists of all those vertices lying on a \(u-v\) geodesic in \(G\) . Given a set \(S\) of vertices of \(G\) , the union of all sets \(H(u,v)\) for \(u,v\in S\) is denoted by \(H(S)\) . A convex set \(S\) satisfies \(H(S)=S\) . The convex hull \([S]\) is the smallest convex set containing \(S\) . The hull number \(h(G)\) is the minimum cardinality among the subsets \(S\) of \(V(G)\) with \([S]=V(G)\) . A set \(S\) is a geodetic set if \(H(S)=V(G)\) ; while \(S\) is a hull set if \([S]=V(G)\) . The minimum cardinality of a geodetic set of \(G\) is the geodetic number \(g(G)\) . A subset \(T\) of a minimum hull set \(S\) is called a forcing subset for \(S\) if \(S\) is the unique minimum hull set containing \(T\) . The forcing hull number \(f(S,h)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\) , and the forcing hull number \(f(G,h)\) of \(G\) is the minimum forcing hull number among all minimum hull sets of \(G\) . The forcing geodetic number \(f(S,g)\)  of a minimum geodetic set \(S\) in \(G\) and the forcing geodetic number \(f(G,g)\) of \(G\) are defined in a similar fashion. The forcing hull numbers of several classes of graphs are determined. It is shown that for integers \(a,b\) with \(0\leq a\leq b\) , there exists a connected graph \(G\) such that \(f(G,h)=a\) and \(h(G)=b\) . We investigate the realizability of integers \(a,b\geq0\) that are the forcing hull and forcing geodetic numbers, respectively, of some graph.

I.J. Dejter1
1 Department of Mathematics and Computer Science University of Puerto Rico, Rfo Piedras, PR 00931-3355
Abstract:

Let \(C\) be a perfect 1-error-correcting code of length \(15\). We show that a quotient \(H(C)\) of the minimum distance graph of \(C\) constitutes an invariant for \(C\) more sensible than those studied up to the present, namely the kernel dimension and the rank. As a by-product, we get a nonlinear Vasil’ev code \(C\) all of whose associated Steiner triple systems are linear. Finally, the determination of \(H(C)\) for known families of \(C\)’s is presented.

Takaaki Hishida1, Kengo Ishikawa 2, Masakazu Jimbo3, Sanpei Kagevama4, Shinji Kuriki5, Osaka Prefecture6
1Department of Information Science Gifu. University 1-1, Yanagido, Gifu, 501-1193, JAPAN
2 Department of Mathematical Sciences Osaka Prefecture University 1-1, Gakuen-cho, Sakai, Osaka, 599-8531, JAPAN
3Department of Mathematics Keio University 3-14-1, Hivoshi. Kohoku-ku, Yokohama, 223-8522, JAPAN
4Department of Mathematics Hiroshima University 1-1-1, Kagamivama. Higashi-Hiroshima. 739-8524, JAPAN
5 Department of Mathematical Sciences
6 University 1-1, Gakuen-cho. Sakai, Osaka, 599-8531, JAPAN
Abstract:

A computer search shows that there does not exist a nested BIB design \(\text{NB}(10, 15, 2, 3)\).

Jiirgen Bierbrauer1
1Department of Mathematical Sciences Michigan Technological University Houghton, Michigan 49931 (USA)
Abstract:

We construct several families of simple 4-designs, which are closely related to Alltop’s series with parameters \(4-(2^f+1,5,5)\), \(f\) odd. More precisely, for every \(q=2^f\), where \(gcd(f,6)=1\), \(f\geq5\), we construct designs with the following parameters:

\[4-(q+1,6,\lambda),\, \text{where}\, \lambda\in\{60,70,90,100,150,160\},\]
\[4-(q+1,8,35),\]
\[4-(q+1,9,\lambda),\, \text{where}\, \lambda\in\{63,147\}.\]

Arnold Knopfmacher1, Neville Robbins2
1 Centre for Applicable Analysis and Number Theory University of the Witwatersrand Johannesburg, South Africa
2 Mathematics Departinent San Francisco State University San Francisco, CA 94132
Abstract:

Eulerian numbers may be defined recursively and have applications to many branches of mathematics. We derive some congruence and divisibility properties of Eulerian numbers.

G.Lo Faro1, H. Shen2
1Department of Mathematics University of Messina Contrada Papardo, Salita Sperone 31 98166 Sant’ Agata, Messina, Italy
2Department of Applied Mathematics Shanghai Jiao Tong University Shanghai 200030, China
Abstract:

In this paper, we determine the spectrum of support sizes of indecomposable threefold triple systems of order \(v\) for all \(v > 15\).

I. M. Wanless1
1Christ Church St Aldates, Oxford OX1 1DP, U-K.
Abstract:

A Latin square is \(N_e\) if it has no intercalates (Latin subsquares of order \(2\)). We correct results published in an earlier paper by McLeish, dealing with a construction for \(N_2\) Latin squares.

Hong Wang1
1Department of Mathematics The University of Idaho Moscow, ID 83844
Abstract:

In [13], we conjectured that if \(G = (V_1, V_2; E)\) is a bipartite graph with \(|V_1| = |V_2| = 2k\) and minimum degree at least \(k + 1\), then \(G\) contains \(k\) vertex-disjoint quadrilaterals. In this paper, we propose a more general conjecture: If \(G = (V_1, V_2; E)\) is a bipartite graph such that \(|V_1| = |V_2| = n \geq 2\) and \(\delta(G) \geq [n/2] + 1\), then for any bipartite graph \(H = (U_1, U_2; F)\) with \(|U_1| \leq n, |U_2| \leq n\) and \(\Delta(H) \leq 2, G\) contains a subgraph isomorphic to \(H\). To support this conjecture, we prove that if \(n = 2k + t\) with \(k \geq 0\) and \(t \geq 3, G\) contains \(k + 1\) vertex-disjoint cycles covering all the vertices of \(G\) such that \(k\) of them are quadrilaterals.

Siaw-Lynn Ng1, Peter R. Wild1
1Maths Department, Royal Holloway Egham, Surrey TW20 0EX, UK
Abstract:

In a finite projective plane, a \(k\)-arc \(\mathcal{K}\) covers a line \(l_0\) if every point on \(l_0\) lies on a secant of \(\mathcal{K}\). Such \(k\)-arcs arise from determining sets of elements for which no linear \((n, q, t)\)-perfect hash families exist [1], as well as from finding sets of points in \(\mathrm{AG}(2, q)\) which determine all directions [2]. This paper provides a lower bound on \(k\) and establishes exactly when the lower bound is attained. This paper also gives constructions of such \(k\)-arcs with \(k\) close to the lower bound.

Antoaneta Klobucar1
1Ekonomski fakultet HR-31000 Osijek Croatia
Abstract:

In this paper we determine the \(k\)-domination number \(\gamma_k\) of \(P_{2k+2} \times P_n\) and \(\lim_{{m,n} \to \infty} \frac{\Gamma_k(P_m \times P_n)}{mn}\).

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;