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.

Paul Renteln1,2
1Department of Physics California State University San Bernardino, CA 92407
2Department of Mathematics California Institute of Technology Pasadena, CA 91125
Abstract:

Let \(G\) be a graph, \(\overline{G}\) its complement, \(L(G)\) its line graph, and \(\chi(G)\) its chromatic number. Then we have the following

THEOREM Let \(G\) be a graph with \(n\) vertices. (i) If \(G\) is triangle
free, then

\[n-4 \leq \chi\left(\overline{L(\overline{G})}\right)\leq n-2\]

(ii) If G is planar and every triangle bounds a disk, then

\[n-3 \leq \chi\left(\overline{L(\overline{G})}\right)\leq n-2\]

R. Haas1, D. Hanson2, G. MacGillivray3
1Department of Mathematics, Smith College Northampton MA 01063
2Department of Mathematics & Statistics University of Regina, Regina SK, Canada S4S 0A2
3Department of Mathematics & Statistics University of Victoria P.O. Box3045 STN CSC Victoria BC, Canada V8W 3P4
Abstract:

Let \(G\) be a simple graph on \(n\) vertices with list chromatic number \(\chi_\ell = s\). If each vertex of \(G\) is assigned a list of \(t\) colours, Albertson, Grossman, and Haas [1] asked how many of the vertices, \(\lambda_{t,s}\), are necessarily colourable from these lists? They conjectured that \(\lambda_{t,s} \geq \frac{tn}{s}\). Their work was extended by Chappell [2]. We improve the known lower bounds for \(\lambda_{t,s}\).

Margaret A.Francel1, David J.John2
1Department of Mathematics and Computer Science The Citadel, Charleston, SC, 29409
2Department of Computer Science Wake Forest University, Winston-Salem, NC, 27109
Abstract:

In general, the class of threshold hypergraphs and decomposable hypergraphs are not equal. In this paper, we show however that, except for two counter examples, a decomposition hypergraph consisting of five or fewer classes is in fact threshold. In the process of showing this result, the paper generates all decomposable quotients with five or fewer classes.

Muktar Elzobi1, Zbigniew Lonc1
1Department of Mathematics and Information Sciences Warsaw University of Technology 00-661 Warsaw, Poland
Abstract:

In this paper, we show that for every sufficiently large integer \(n\) and every positive integer \(c \leq \left\lfloor \frac{1}{6}({\log \log n})^\frac{1}{2} \right \rfloor\), a Boolean lattice with \(n\) atoms can be partitioned into chains of cardinality \(c\), except for at most \(c-1\) elements which also form a chain.

Vassil Yorgov1, Radka Russeva2
1Department of Mathematical Sciences Michigan Technological University Houghton, MI 49931
2Department of Mathematics and Computer Science Shoumen University, Shoumen 9712, Bulgaria
Abstract:

We construct all self-dual \([24, 12, 8]\) quaternary codes with a monomial automorphism of prime order \(r > 3\) and obtain a unique code for \(r = 23\) (which has automorphisms of orders \(5\), \(7\), and \(11\) too), two inequivalent codes for \(r = 11\), \(6\) inequivalent codes for \(r = 7\), and \(12\) inequivalent codes for \(r = 5\). The obtained codes have \(12\) different weight spectra.

Peter Adams1, Elizabeth J.Billington1, E.S. Mahmoodian 2
1Centre for Discrete Mathematics and Computing, Department of Mathematics, The University of Queensland, Queensland 4072 AUSTRALIA
2 Department of Mathematical Sciences Sharif University of Technology P.O. Box 11365-9415 Tehran, LR. IRAN
Abstract:

Metamorphoses of small \(k\)-wheel systems for \(k = 3, 4,\) and \(6\) are obtained. In particular, we obtain simultaneous metamorphoses of: \(3\)-wheel systems into Steiner triple systems and into \(K_{1,3}\)-designs; \(4\)-wheel systems into \(4\)-cycle systems, \(K_{1,4}\)-designs, and bowtie systems; \(6\)-wheel systems into \(6\)-cycle systems, \(K_{1,6}\)-designs, and \(3\)-windmill designs or near-\(3\)-windmill designs.

Martin Baza1, Mirka Miller2
1 Department of Applied Mathematics, Technical University, Letna 9, 042 00 Koaice, Slovak Republic
2Department of Computer Science and Software Engineering, University of Newcastle, NSW 2308, Australia
Abstract:

We deal with the problem of labeling the vertices, edges, and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all the faces constitute an arithmetical progression of difference \(d\).

M.M. Cropper1, J.L. Goldwasser2
1Dept. of Mathematics, Eastern Kentucky University, Richmond, KY 40475
2 Dept. of Mathematics, West Virginia University, Morgantown, WV 26506
Abstract:

If \(L\) is a list assignment function and \(\kappa\) is a multiplicity function on the vertices of a graph \(G\), a certain condition on \((G, L, \kappa)\), known as Hall’s multicoloring condition, is obviously necessary for the existence of a multicoloring of the vertices of \(G\). A graph \(G\) is said to be in the class \(MHC\) if it has a multicoloring for any functions \(L\) and \(\kappa\) such that \((G, L, \kappa)\) satisfies Hall’s multicoloring condition. It is known that if \(G\) is in \(MHC\) then each block of \(G\) is a clique and each cutpoint lies in precisely two blocks. We conjecture that the converse is true as well. It is also known that if \(G\) is a graph consisting of two cliques joined at a point then \(G\) is in \(MHC\). We present a new proof of this result which uses common partial systems of distinct representatives, the relationship between matching number and vertex covering number for 3-partite hypergraphs, and Menger’s Theorem.

Charles Cadogan1
1Department of Computer Science, Mathematics & Physics University of the West Indies Cave Hill Campus Barbados, West Indies
Abstract:

This paper presents a new approach in the quest for a solution to the \(3x+1\) problem. The method relies on the convergence of the trajectories of the odd positive integers by exploiting the role of the positive integers of the form \(1+4n\), where \(n\) is a non-negative integer.

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;