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.

LeRoy B. Beasley1
1Box C-3, Ste 317 Clocktower Plaza, 550 N. Main Logan, Utah 84321, U.S.A
Abstract:

Let \( m \) and \( n \) be positive integers, and let \( R = (r_1, \ldots, r_m) \) and \( S = (s_1, \ldots, s_n) \) be non-negative integral vectors. Let \( \mathcal{A}(R, S) \) be the set of all \( m \times n \) \((0,1)\)-matrices with row sum vector \( R \) and column vector \( S \). Let \( R \) and \( S \) be non-increasing, and let \( F(R, S) \) be the \( m \times n \) \((0,1)\)-matrix where for each \( i \), the \( i^{\text{th}} \) row of \( F(R, S) \) consists of \( r_i \) 1’s followed by \( n – r_i \) 0’s, called Ferrers matrices. The discrepancy of an \( m \times n \) \((0,1)\)-matrix \( A \), \( \text{disc}(A) \), is the number of positions in which \( F(R, S) \) has a 1 and \( A \) has a 0. In this paper we investigate linear operators mapping \( m \times n \) matrices over the binary Boolean semiring to itself that preserve sets related to the discrepancy. In particular we characterize linear operators that preserve both the set of Ferrers matrices and the set of matrices of discrepancy one.

Jamie Hallas 1, Mohra Zayed 1, Ping Zhang1
1Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
Abstract:

The line graph \( L(G) \) of a nonempty graph \( G \) has the set of edges in \( G \) as its vertex set where two vertices of \( L(G) \) are adjacent if the corresponding edges of \( G \) are adjacent. Let \( k > 2 \) be an integer and let \( G \) be a graph containing k-paths (paths of order \( k \)). The k-path graph \( P_k(G) \) of \( G \) has the set of k-paths of \( G \) as its vertex set where two distinct vertices of \( P_k(G) \) are adjacent if the corresponding k-paths of \( G \) have a \( (k-1) \)-path in common. Thus, \( P_2(G) = L(G) \) and \( P_3(G) = L(L(G)) \). Hence, the k-path graph \( P_k(G) \) of a graph \( G \) is a generalization of the line graph \( L(G) \). Let \( G \) be a connected graph of order \( n > 3 \) and let \( k \) be an integer with \( 2 < k 2 \), then \( P_3(T) \) is \( k \)-tree-connected. This conjecture was verified for \( k = 2, 3 \). In this work, we show that if \( T \) is a tree of order at least 6 containing no vertices of degree 2, 3, 4, or 5, then \( P_3(T) \) is 4-tree-connected and so verify the conjecture for the case when \( k = 4 \).

Ramy Shaheen1, Suhail Mahfud1, Qays Alhawat1
1Department of Mathematics, Faculty of Science Tishreen University, Lattakia, Syria.
Abstract:

Let \( G(V,E) \) be a simple connected graph with vertex set \( V \) and edge set \( E \). The Wiener index in the graph is \(W(G) = \sum_{\{u,v\} \subseteq V} d(u,v),\) where \( d(u,v) \) is the distance between \( u \) and \( v \), and the Hosoya polynomial of \( G \) is \(H(G, x) = \sum_{\{u,v\} \subseteq V} x^{d(u,v)}.\) The hyper-Wiener index of \( G \) is \(WW(G) = \frac{1}{2} \left( W(G) + \sum_{\{u,v\} \subseteq V} d^2(u,v) \right).\) In this paper, we compute the Wiener index, Hosoya polynomial, and hyper-Wiener index of Jahangir graph \( J_{8,m} \) for \( m \geq 3 \).

Anetta Szynal-Liana1, Iwona Włoch 1
1Faculty of Mathematics and Applied Physics, Rzeszow University of Technology, al. Powstanców ´ Warszawy 12, 35-959 Rzeszów, Poland
Abstract:

Hybrid numbers are generalization of complex, hyperbolic and dual numbers. In this paper we introduce and study Fibonacci-Pell hybrinomials, i.e. polynomials, which are a generalization of hybrid numbers of the Fibonacci type.

Sultan Senan Mahde1, Veena Mathad1
1Department of Studies in Mathematics, University of Mysore, Manasagangotri, Mysuru , India
Abstract:

The hub-integrity of a graph is given by the minimum of \( |S| + m(G – S) \), where \( S \) is a hub set and \( m(G – S) \) is the maximum order of the components of \( G – S \). In this paper, the concept of hub edge-integrity is introduced as a new measure of the stability of a graph \( G \), and it is defined as \(HEI(G) = \min\{|S| + m(G – S)\},\) where \( S \) is an edge hub set and \( m(G – S) \) is the order of a maximum component of \( G – S \). Furthermore, an \( HEI \)-set of \( G \) is any set \( S \) for which this minimum is attained. Several properties and bounds on the \( HEI \) are presented, and the relationship between \( HEI \) and other parameters is investigated. The \( HEI \) of some classes of graphs is also computed.

Ali Ahmad1
1College of Computer Science and Information Technology,, Jazan University, Jazan, Saudi Arabia.
Abstract:

A graph \( G(R) \) is said to be a zero divisor graph of a commutative ring \( R \) with identity if \( x_1, x_2 \in V(G(R)) \) and \( (x_1, x_2) \in E(G(R)) \) if and only if \( x_1 \cdot x_2 = 0 \). The vertex-degree-based eccentric topological indices of zero divisor graphs of commutative rings \( \mathbb{Z}_{p^2} \times \mathbb{Z}_{q^2} \) are studied in this paper, with \( p \) and \( q \) being primes.

Matthias Kunik1
1Universität Magdeburg, IAN, Gebäude 02, Universitätsplatz 2, D-39106 Magdeburg, Germany
Abstract:

The sums \( S(x, t) \) of the centered remainders \( kt – \lfloor kt \rfloor – 1/2 \) over \( k \leq x \) and corresponding Dirichlet series were studied by A. Ostrowski, E. Hecke, H. Behnke, and S. Lang for fixed real irrational numbers \( t \). Their work was originally inspired by Weyl’s equidistribution results modulo 1 for sequences in number theory.

In a series of former papers, we obtained limit functions which describe scaling properties of the Farey sequence of order \( n \) for \( n \to \infty \) in the vicinity of any fixed fraction \( a/b \) and which are independent of \( a/b \). We extend this theory on the sums \( S(x, t) \) and also obtain a scaling behavior with a new limit function. This method leads to a refinement of results given by Ostrowski and Lang and establishes a new proof for the analytic continuation of related Dirichlet series. We will also present explicit relations to the theory of Farey sequences.

Kimmo Eriksson1, Markus Jonsson2, Jonas Sjöstrand 3
1Mälardalen University, School of Education, Culture and Communication,, Box 883, SE-72123 Västerås, Sweden
2Stockholm University, Centre for Cultural Evolution,, SE-10691 Stockholm, Sweden
3Mälardalen University, School of Education, Culture and Communication,, Box 883, SE-72123 Västerås, Sweden (corresponding author)
Abstract:

Bulgarian solitaire is played on \( n \) cards divided into several piles; a move consists of picking one card from each pile to form a new pile. This can be seen as a process on the set of integer partitions of \( n \): if sorted configurations are represented by Young diagrams, a move in the solitaire consists of picking all cards in the bottom layer of the diagram and inserting the picked cards as a new column. Here we consider a generalization, \( L \)-solitaire, wherein a fixed set of layers \( L \) (that includes the bottom layer) are picked to form a new column.

\( L \)-solitaire has the property that if a stable configuration of \( n \) cards exists it is unique. Moreover, the Young diagram of a configuration is convex if and only if it is a stable (fixpoint) configuration of some \( L \)-solitaire. If the Young diagrams representing card configurations are scaled down to have unit area, the stable configurations corresponding to an infinite sequence of pick-layer sets \( (L_1, L_2, \ldots) \) may tend to a limit shape \( \phi \). We show that every convex \( \phi \) with certain properties can arise as the limit shape of some sequence of \( L_n \). We conjecture that recurrent configurations have the same limit shapes as stable configurations.

For the special case \( L_n = \{1, 1 + \lfloor 1/q_n \rfloor, 1 + \lfloor 2/q_n \rfloor, \ldots\} \), where the pick layers are approximately equidistant with average distance \( 1/q_n \) for some \( q_n \in (0,1] \), these limit shapes are linear (in case \( nq_n^2 \to 0 \)), exponential (in case \( nq_n^2 \to \infty \)), or interpolating between these shapes (in case \( nq_n^2 \to C > 0 \)).

Abdul Rauf Nizami1, Asim Naseem2, Hafiz Muhammad Waqar Ahmed2
1Faculty of Information Technology, University of Central Punjab, Lahore-Pakistan
2Department of Mathematics, GC University, Lahore-Pakistan
Abstract:

We introduce a polygonal cylinder \( C_{m,n} \), using the Cartesian product of paths \( P_m \) and \( P_n \) and using topological identification of vertices and edges of two opposite sides of \( P_m \times P_n \), and give its Hosoya polynomial, which, depending on odd and even \( m \), is covered in seven separate cases.

Anthony Van Duzer1
1Department of Mathematics, University of Florida, Gainesville, Florida 32601 Current address: Department of Mathematics, University of Florida, Gainesville, Florida 32611
Abstract:

In this paper we find recurrence relations for the asymptotic probability a vertex is \(k\) protected in all Motzkin trees. We use a similar technique to calculate the probabilities for balanced vertices of rank \(k\). From this we calculate upper and lower bounds for the probability a vertex is balanced and upper and lower bounds for the expected rank of balanced vertices.

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;