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.

M. Cera1, A. Dianez2, P. Garcia-Vazquez1, J.C. Valenzuela3
1E.U.LT. Agricola, Universidad de Sevilla, Spain.
2E.T.S. Arquitectura, Universidad de Sevilla, Spain.
3E.P.S. Algeciras, Universidad de Cédiz, Spain.
Abstract:

The study of the maximum size \(ex(n; K_{t,t})\) of a graph of order \(n\) not containing the complete bipartite graph \(K_{t,t}\) as a subgraph is the aim of this paper. We show an upper bound for this extremal function that is optimum for infinitely many values of \(n\) and \(t\). Moreover, we characterize the corresponding family of extremal graphs.

Garth Isaak1, Kathryn L.Nyman2, Ann N.Trenk3
1Department of Mathematics Lehigh University Lehigh, PA 18015
2Department of Mathematics Cornell University Ithaca, NY 14853
3Department of Mathematics Wellesley College Wellesley, MA 02481
Abstract:

In this paper we extend the work of Bogart and Trenk [3] and Fishburn and Trotter [6] in studying different classes of bitolerance orders. We provide a more comprehensive list of classes of bitolerance orders and prove equality between some of these classes in general and other classes in the bipartite domain. We also provide separating examples between unequal classes of bitolerance orders.

Alois Panholzer1
1Institute FOR ALGEBRA AND COMPUTER MATHEMATICS, TECHNISCHE UNIVERSITAT Wien, WiEDNER HAUPTSTRASSE 8-10, A- 1040 WIEN, AUSTRIA.
Abstract:

We consider non-crossing trees and show that the height of node \(\rho n\) with \(0 < p < 1\) in a non-crossing tree of size \(n\) is asymptotically Maxwell-distributed. We also give an asymptotic formula for the expected height of node \(\rho n\).

Shung-Liang Wu1
1National Lien-Ho Institute of Technology Miaoli, Taiwan, R. O. C.
Abstract:

Let \(G = (V(G), E(G))\) be a finite simple graph with \(p\) vertices and \(n\) edges. A labeling of \(G\) is an injection \(f: V(G) \to {Z}_n\). A labeling of \(G\) is called \(2\)-sequential if \(f(V(G)) = \{r, r+1, \ldots, r+p-1\}\) (\(0 \leq r <r+ p-1 \leq n-1\)) and the induced edge labeling \(f^*: E(G) \to \{0, 1, \ldots, n-1\}\) given by \[f^*(u,v) = f(u) + f(v), \quad \text{for every edge } (u,v) \] forms a sequence of distinct consecutive integers \(\{k, k+1, \ldots, n+k-1\}\) for some \(k\) (\(1 \leq k \leq n-2\)). By utilizing the graphs having \(2\)-sequential labeling, several new families of sequential graphs are presented.

Akira Saito1, Tomoki Yamashita2
1Department of Applied Mathematics, Nihon University Sakurajosui 3-25-40 Setagaya-Ku, Tokyo 156-8550 JAPAN
2Department of Mathematics, Kobe University Rokkodai 1~1, Nada-ku, Kobe 657-8501 JAPAN
Abstract:

A cycle \(C\) in a graph \(G\) is said to be a dominating cycle if every vertex of \(G\) has a neighbor on \(C\). Strengthening a result of Bondy and Fan [3] for tough graphs, we prove that a \(k\)-connected graph \(G\) (\(k \geq 2\)) of order \(p\) with \(t(G) > \frac{k}{k+1}\) has a dominating cycle if \(\sum_{x \in S} \geq p – 2k – 2\) for each \(S \subset V(G)\) of order \(k+1\) in which every pair of vertices in \(S\) have distance at least four in \(G\).

Diane Donovan1, Abdollah Khodkar1
1Centre for Discrete Mathematics and Computing Department of Mathematics The University of Queensland Queensland 4072 Australia
Abstract:

Let \( T \) be a partial Latin square. If there exist two distinct Latin squares \( M \) and \( N \) of the same order such that \( M \cap N = T \), then \( M \setminus T \) is said to be a Latin trade. For a given Latin square \( M \), it is possible to identify a subset of entries, termed a critical set, which intersects all Latin trades in \( M \) and is minimal with respect to this property.

Stinson and van Rees have shown that under certain circumstances, critical sets in Latin squares \( M \) and \( N \) can be used to identify critical sets in the direct product \( M \times N \). This paper presents a refinement of Stinson and van Rees’ results and applies this theory to prove the existence of two new families of critical sets.

Spencer P.Hurd1, Tarsem S.Purewal2, Dinesh G.Sarvate3
1Dept. of Mathematics and CS, The Citadel Charleston, SC, 29409,
2Department of Mathematics, University of Charleston, Charleston, SC, 29424,
3Department of Mathematics, University of Charleston, Charleston, SC, 29424
Abstract:

We obtain necessary conditions for the enclosing of a group divisible design with block size 3, \( \text{GDD}(n, m; \lambda) \), into a group divisible design \( \text{GDD}(\text{n}, \text{m+1}; \lambda+\text{x}) \) with one extra group and minimal increase in \( \lambda \). We prove that the necessary conditions are sufficient for the existence of all such enclosings for GDDs with group size 2 and \( \lambda \leq 6 \), and for any \( \lambda \) when \( v \) is sufficiently large relative to \( \lambda \).

Peter J.Larcombe1, David R.French1
1School of Computing and Technology University of Derby, Kedleston Road, Derby DE22 1GB, U.K.
Abstract:

A known convolution identity involving the Catalan numbers is presented and discussed. Catalan’s original formulation, which is algebraically straightforward, is similar in style to one reported previously by the first author and the result has some interesting combinatorial aspects.

A. Panayotopoulos1, P. Tsikouras1
1 Department of Informatics University of Piraeus 80 Karaoli & Dimitriou, 185 34 Piraeus Greece
Abstract:

In this paper we prove various properties of the meanders. We then use these properties in order to construct recursively the set of all meanders of any particular order.

Hossein Shahmohamad1
1Department of Mathematics & Statistics Rochester Institute of Technology, Rochester, NY 14623
Abstract:

The main results of this paper are the discovery of infinite families of flow equivalent pairs of \( B_5 \) and \( W_5 \), amalamorphs, and infinite families of chromatically equivalent pairs of \( P \) and \( W_5^* \); homeomorphs, where \( B_5 \) is \( K_5 \) with one edge deleted, \( P \) is the Prism graph, and \( W_5 \) is the join of \( K_1 \) and a cycle on 4 vertices. Six families of \( B_5 \) amalamorphs, with two families having 6 parameters, and 9 families of \( W_5 \) amalamorphs, with one family having 4 parameters, are discovered. Since \( B_5 \) and \( W_5 \) are both planar, all these results obtained can be stated in terms of chromatically equivalent pairs of \( B_5^* \) and \( W_5^* \) homeomorphs. Also, three conjectures are made about the non-existence of flow-equivalent amalamorphs or chromatically equivalent homeomorphs of certain 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;