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.

Michael Ackerman1, Ralph J.Faudree2
1Department of Mathematics Bellarmine University Louisville, KY 40205
2Department of Mathematical Sciences University of Memphis Memphis, TN 38152
Abstract:

Many different approaches exist in studying graphs with high connectivity and small diameter. We consider the effect of deleting vertices and edges from a graph while maintaining a small diameter. The following property is introduced: A graph \( G \) has property \( B_{d,i,j} \) if and only if after the removal of at most \( i \) vertices and at most \( j \) edges, the resulting graph has diameter at most \( d \) and is not the trivial graph on one vertex. The central theme of this paper is to investigate the structure of graphs that have property \( B_{d,i,j} \) and to investigate the structure that is needed to imply that a graph has property \( B_{d,i,j} \). Lower bounds on minimum degree and connectivity that imply property \( B_{d,i,j} \) for specific values of \( d \) are found. These bounds are also shown to be sharp in all but one case.

Darryn Bryan1, Mike Grannell2, Terry Griggs2
1Centre for Discrete Mathematics and Computing Department of Mathematics The University of Queensland Queensland 4072 AUSTRALIA
2Department of Pure Mathematics The Open University Walton Hall Milton Keynes MK7 6AA UNITED KINGDOM
Abstract:

An \( m \)-cycle system of order \( v \), denoted by \( mCS(v) \), is a decomposition of the complete graph \( K_v \) into \( m \)-cycles. We discuss two types of large sets of \( mCS(v) \) and construct examples of both types for \( (m,v) = (4,9) \) and one type for \( (m,v) = (6,9) \). These are the first large sets of cycle systems constructed with \( m > 3 \), apart from the Hamiltonian cycle decompositions given in [2].

Gary Chartrand1, Henry Escuadro1, Ping Zhang1
1Department of Mathematics Western Michigan University Kalamazoo, MI 49008 USA
Abstract:

For two vertices \( u \) and \( v \) in a connected graph \( G \), the detour distance \( D(u,v) \) from \( u \) to \( v \) is defined as the length of a longest \( u-v \) path in \( G \). The detour eccentricity \( e_D(v) \) of a vertex \( v \) in \( G \) is the maximum detour distance from \( v \) to a vertex of \( G \). The detour radius \( \text{rad}_D(G) \) of \( G \) is the minimum detour eccentricity among the vertices of \( G \), while the detour diameter \( \text{diam}_D(G) \) of \( G \) is the maximum detour eccentricity among the vertices of \( G \). It is shown that \(\text{rad}_D(G) < \text{diam}_D(G) < 2\text{rad}_D(G)\) for every connected graph \( G \) and that every pair \( a,b \) of positive integers with \( a \leq b \leq 2a \) is realizable as the detour radius and detour diameter of some connected graph. The detour center of \( G \) is the subgraph induced by those vertices of \( G \) having detour eccentricity \( \text{rad}_D(G) \). A connected graph \( G \) is detour self-centered if \( G \) is its own detour center. The detour periphery of \( G \) is the subgraph induced by the vertices of \( G \) having detour eccentricity \( \text{diam}_D(G) \). It is shown that every graph is the detour center of some connected graph. Detour self-centered graphs are investigated. We present sufficient conditions for a graph to be the detour periphery of some connected graph. Several classes of graphs that are not the detour periphery of any connected graph are determined.

Michael D.Hirschhorn1, James A.Sellers2
1School of Mathematics, UNSW, Sydney 2052, Australia
2Department of Mathematics The Pennsylvania State University, 107 Whitmore Lab, University Park, PA 16802
Abstract:

In recent work, Corteel and Lovejoy extensively studied overpartitions as a means of better understanding and interpreting various \( q \)-series identities. Our goal in this article is quite different. We wish to prove a number of arithmetic relations satisfied by the overpartition function. Employing elementary generating function dissection techniques, we will prove identities such as

\[
\sum\limits_{n\geq0}\overline{p}\left(8n + 7\right) q^n = 64 \frac{(q^2)_\infty^{22}}{(q)_\infty^{23}}
\]

and congruences such as

\[
\overline{p}(9n+6) \equiv 0 \pmod{8}
\]

where \( \overline{p}(n) \) denotes the number of overpartitions of \( n \).

Jeffrey L.Poet1, Victor Onkoba2, Dustin Daffron3, Heather Goforth3, Chris Thomas3
1Department of Computer Science, Mathematics, and Physics Missouri Western State College, St. Joseph, Missouri 64507
2MWSC student research assistant
3High school student research assistants (St. Joseph, MO)
Abstract:

Let \( G = (V,E) \) be a graph with \( |V| = p \) and \( |E| = q \). The graph \( G \) is total edge-magic if there exists a bijection \( f : V \cup E \to \{1,2,\ldots,p+q\} \) such that for all \( e = (u,v) \in E \), \( f(u) + f(e) + f(v) \) is constant throughout the graph. A total edge-magic graph is called super edge-magic if \( f(V) = \{1,2,\ldots,p\} \). Lee and Kong conjectured that for any odd positive integer \( r \), the union of any \( r \) star graphs is super edge-magic. In this paper, we supply substantial new evidence to support this conjecture for the case \( r = 3 \).

Ian Anderson1, Leigh H.M.Ellison1
1Department of Mathematics, University of Glasgow University Gardens, Glasgow G12 8QW, UK
Abstract:

We show that \( \mathbb{Z} \)-cyclic ordered triplewhist and directed triplewhist tournaments on \( p \) elements exist when \( p \equiv 9 \pmod{16} \) is prime.

Martin Bata1
1Department of Applied Mathematics Technical University Letna 9, 042 00 Kosice Slovak Republic
Abstract:

If \( G = (V,E,F) \) is a finite connected plane graph on \( |V| = p \) vertices, \( |E| = q \) edges and \( |F| = t \) faces, then \( G \) is said to be \( (a, d) \)-face antimagic iff there exists a bijection \( h: E \to \{1,2,\ldots,q\} \) and two positive integers \( a \) and \( d \) such that the induced mapping \( g_h: F \to \mathbb{N} \), defined by \( g_h(f) = \sum\{h(u,v) : \text{edge } (u,v) \text{ surrounds the face } f\} \), is injective and has the image set \( g_h(F) = \{a,a+d,\ldots,a + (t – 1)d\} \). We deal with \( (a,d) \)-face antimagic labelings for a certain class of plane graphs.

Neil A.Gordon1, Trevor M.Jarvist1, Ron Shaw1
1University of Hull, Hull HU6 7RX, UK
Abstract:

We provide tables which summarize various aspects of the finite linear groups \( \text{GL}(n, 2) \), \( n < 7 \), in their action upon the vector space \( V_n = V(n, 2) \) and upon the associated projective space \( \text{PG}(n – 1, 2) \). It is intended that the tabulated results should be immediately accessible to finite geometers, and to all others (design theorists, coding theorists, \ldots) who have occasional need of these groups. In the case \( n = 4 \) attention is also paid to the maximal subgroup \( \Gamma \text{L}(2, 4) \). In the case \( n = 6 \) the maximal subgroups \( \Gamma \text{L}(2, 8) \) and \( \Gamma \text{L}(3, 4) \) are treated, as are class aspects of the tensor product structure \( V_6 = V_2 \otimes V_3 \), and of the exterior product structure \( V_6 = \wedge^2 V_4 \).

Jerrett Dumouchel1, Saad I. El-Zanati1
1Mathematics Department Illinois State University Normal, Illinois 61790-4520, U.S.A.
Abstract:

It is conjectured that any 2-regular graph \( G \) with \( n \) edges has a \( \rho \)-labeling (and thus divides \( K_{2n+1} \) cyclically). In this note, we show that the conjecture holds when \( G \) has at most two components.

C.C. Lindner1, Antoinette Tripodi2
1Department of Discrete and Statistical Sciences Auburn University Auburn, Alabama 36849 USA
2Departimento di Matematica Universita di Messina 98166 Messina. ITALIA
Abstract:

Let \(K_4\backslash e=…\). If we remove the “diagonal” edge, the result is a \(4\)-cycle. Let \((X,B)\) be a \(K_4\backslash e\) design of order \(n\); i.e., an edge-disjoint decomposition of \(K_n\) into copies of \(K_4\backslash e\). Let \(D(B)\) be the collection of “diagonals” removed from the graphs in \(B\) and \(C(B)\) the resulting collection of \(4\)-cycles. If \(C_2(B)\) is a reassembly of these edges into \(4\)-cycles and \(L\) is the collection of edges in \(D(B)\) not used in a \(4\)-cycle of \(C_2(B)\), then \((X, (C_1(B) \cup C_2(B)), L)\) is a packing of \(K_n\) with \(4\)-cycles and is called a metamorphosis of \((X,B)\). We construct, for every \(n = 0\) or \(1\) (mod \(5\)) \(> 6\), \(n \neq 11\), a \(K_4\backslash e\) design of order \(n\) having a metamorphosis into a maximum packing of \(K_n\) with \(4\)-cycles. There exists a maximum packing of \(K_n\) with \(4\)-cycles, but it cannot be obtained from a \(K_4\backslash e\) design.

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;