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.

D. de Caen1, D. L. Kreher2, J. A. Wiseman3
1Department of Mathematics Queens University Kingston, Ontario K7L 3N6 CANADA
2Department of Mathematics University of Wyoming Laramie, Wyoming 82071 ULS.A.
3Department of Mathematics Rochester Institute of Technology Rochester, New York 14623 ULS.A.
Abstract:

Let \(S\) and \(T\) be sets with \(|S| = m\) and \(|T| = n\). Let \(S_3, S_2\) and \(T_3, T_2\) be the sets of all \(3\)-subsets (\(2\)-subsets) of \(S\) and \(T\), respectively. Define \(Q((m, 2, 3), (n, 2, 3))\) as the smallest subset of \(S_2 \times T_2\) needed to cover all elements of \(S_3 \times T_3\). A more general version of this problem is initially defined, but the bulk of the investigation is devoted to studying this number. Its property as a lower bound for a planar crossing number is the reason for this focus.

Alexander Pott1
1Department of.Mathematics and Statistics Wright State University Dayton, Ohio 45435 USA
Abstract:

Under some assumptions on the incidence matrices of symmetric designs, we prove a non-existence theorem for symmetric designs. The approach generalizes Wilbrink’s result on difference sets \([7]\).

DV. Chopra1
1Wichita State University Wichita, Kansas 67208 U.S.A.
Abstract:

In this paper, we derive some inequalities which the parameters of a two-symbol balanced array \(T\) (\(B\)-array) of strength four must satisfy for \(T\) to exist.

K. J. Danhof1, N.C. K. Phillips1, W. D. Wallis1
1Department of Computer Science Southern Illinois University
Abstract:

This paper considers Latin squares of order \(n\) having \(0, 1, \ldots, n-1\) down the main diagonal and in which the back diagonal is a permutation of these symbols (diagonal squares). It is an open question whether or not such a square which is self-orthogonal (i.e., orthogonal to its transpose) exists for order \(10\). We consider two possible constraints on the general concept: self-conjugate squares and strongly symmetric squares. We show that relative to each of these constraints, a corresponding self-orthogonal diagonal Latin square of order \(10\) does not exist. However, it is easy to construct self-orthogonal diagonal Latin squares of orders \(8\) and \(12\) which satisfy each of the constraints respectively.

B. Du1, L. Zhu1
1Department of Mathematics Suzhou University Suzhou, 215006 People’s Republic of China
Abstract:

It has been conjectured by D. R. Stinson that an incomplete Room square \((n, s)\)-IRS exists if and only if \(n\) and \(s\) are both odd and \(n \geq 3s + 2\), except for the nonexistent case \((n, s) = (5, 1)\). In this paper we shall improve the known results and show that the conjecture is true except for \(45\) pairs \((n, s)\) for which the existence of an \((n, s)\)-IRS remains undecided.

E. Csaki1, S. G. Mohanty2, Jagdish Saran3
1Hungarian Academy of Sciences Budapest, HUNGARY
2 McMaster University Hamilton, Ontario CANADA
3 University of Delhi Delhi, INDIA
Abstract:

Consider a random walk in a plane in which a particle at any stage moves one unit in any one of the four directions, namely, north, south, east, west with equal probability. The problem of finding the distribution of any characteristic of the above random walk when the particle reaches a fixed point \((a, b)\) after \(d\) steps reduces to the counting of lattice paths in a plane in which the path can move one unit in any of the four directions. In this paper, path counting results related to the boundaries \(y-x = k_1\) and \(y+x = k_2\) such as touchings, crossings, etc., are obtained by using either combinatorial or probabilistic methods. Some extensions to higher dimensions are indicated.

William McCuaig1
1Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario, N2L 3G1 CANADA
Abstract:

For \(v \geq 4\) we determine the largest number \(f(v)\), such that every simple \(3\)-connected graph on \(v\) vertices has \(f(v)\) edge contractions which result in a smaller \(3\)-connected graph. We also characterize those simple \(3\)-connected graphs on \(v\) vertices which have exactly \(f(v)\) such edge contractions.

Olof Heden 1
1Department of Mathematics Royal Institute of Technology Stockholm, Sweden
B. Piazza1, R. Ringeisen2, S. Stueckle3
1University of Southem Mississippi
2 Clemson University
3University of Idaho
Abstract:

Several measures of the vulnerability of a graph have been examined previously. These include connectivity, toughness, binding number, and integrity. In this paper the authors examine the toughness and binding number of cycle permutation graphs (sometimes called generalized prisms). In particular, we determine the binding number for any cycle permutation graph and find upper and lower bounds for the toughness of such graphs. A class of cycle permutation graphs where the lower bound is always achieved and a class of cycle permutation graphs (which are also generalized Petersen graphs) where the lower bound is never achieved are also presented.

Howard B. Frost1, Michael S. Jacobson2, Jerald A. Kabell3, F.R. MeMorris2
1 Department of Mathematics University of Arizona Tucson, AZ 85721
2 Department of Mathematics University of Louisville Louisville, KY 40292
3Department of Computer Science Central Michigan University Mt. Pleasant, MI 48859
Abstract:

Following up on the bipartite analogue of an interval graph developed in a previous work, we investigate several possibilities for a bipartite analogue of the concept of a split graph. We also give bipartite analogues of threshold graphs and of perfect 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;