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.

Bader Ali1, Abdullah Al Mutairi1, Paul Manuel1
1Bader Ali, Abdullah Al Mutairi, and Paul Manuel Department of Information Science, College of Computing Science and Engineering, Kuwait University, Kuwait
Abstract:

A set \( S \) of vertices of a graph \( G(V,E) \) is a \({dominating \;set}\) if every vertex of \( V \setminus S \) is adjacent to some vertex in \( S \). A dominating set is said to be \({efficient}\) if every vertex of \( V \setminus S \) is dominated by exactly one vertex of \( S \). A paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. A set \( S \) of vertices in \( G \) is a total dominating set of \( G \) if every vertex of \( V \) is adjacent to some vertex in \( S \). In this paper, we construct a minimum paired dominating set and a minimum total dominating set for the infinite diamond lattice. The total domatic number of \( G \) is the size of a maximum cardinality partition of \( V \) into total dominating sets. We also demonstrate that the total domatic number of the infinite diamond lattice is 4.

Frederick V. Henle1, James M. Henle1
1Department of Mathematics and Statistics, Smith College, 44 College Lane, Northampton, Massachusetts, USA
Abstract:

A set of natural numbers tiles the plane if a square-tiling of the plane exists using exactly one square of side length n for every n in the set. In [9] it is shown that N, the set of all natural numbers, tiles the plane. We answer here a number of questions from that paper. We show that there is a simple tiling of the plane (no nontrivial subset of squares forms a rectangle). We show that neither the odd numbers nor the prime numbers tile the plane. We show that N can tile many, even infinitely many planes.

Walaa Asakly1, Toufik Mansour 1
1Department of Mathematics, University of Haifa, 3498838 Haifa, Israel
Abstract:

Let \( s, t \) be any numbers in \( \{0,1\} \) and let \( \pi = \pi_1 \pi_2 \cdots \pi_m \) be any word. We say that \( i \in [m-1] \) is an \( (s,t) \)-parity-rise if \( \pi_i \equiv s \pmod{2} \), \( \pi_{i+1} \equiv t \pmod{2} \), and \( \pi_i < \pi_{i+1} \). We denote the number of occurrences of \( (s,t) \)-parity-rises in \( \pi \) by \( \text{rise}_{s,t}(\pi) \). Also, we denote the total sizes of the \( (s,t) \)-parity-rises in \( \pi \) by \( \text{size}_{s,t}(\pi) \), that is, \( \text{size}_{s,t}(\pi) = \sum_{\pi_i < \pi_{i+1}} (\pi_{i+1} – \pi_i). \) A composition \( \pi = \pi_1 \pi_2 \cdots \pi_m \) of a positive integer \( n \) is an ordered collection of one or more positive integers whose sum is \( n \). The number of summands, namely \( m \), is called the number of parts of \( \pi \). In this paper, by using tools of linear algebra, we found the generating function that counts the number of all compositions of \( n \) with \( m \) parts according to the statistics \( \text{rise}_{s,t} \) and \( \text{size}_{s,t} \), for all \( s, t \).

Bai-Ni Guo1, Feng Qi2
1COLLEGE OF MATHEMATICS, INNER MONGOLIA UNIVERSITY FOR NATIONALITIES, TONGLIAO CITY, INNER MONGOLIA AUTONOMOUS REGION, 028043, CHINA;
2DEPARTMENT OF MATHEMATICS, COLLEGE OF SCIENCE, TIANJIN POLYTECHNIC UNIVERSITY, TIANJIN CITY, 300387, CHINA
Abstract:

In the paper, utilizing respectively the induction, a generating function of the Lah numbers, the Chu-Vandermonde summation formula, an inversion formula, the Gauss hypergeometric series, and two generating functions of Stirling numbers of the first kind, the authors collect and provide six proofs for an identity of the Lah numbers.

Jeremy Chapman1, Adriano Marzullo2
1DEPARTMENT OF MATHEMATICS, LYON COLLEGE, 2300 HIGHLAND ROAD, BATESVILLE, AR, USA
2DEPARTMENT OF MATHEMATICS, BECKER COLLEGE, 61 SEVER STREET, WORCESTER, MA, USA
Abstract:

We prove that if \( A \subset \mathbb{Z}_q \setminus \{0\} \), \( A \neq \langle p \rangle \), \( q = p^\ell \), \( \ell \geq 2 \) with \( |A| > C \sqrt[3]{\sqrt{\ell}^2 q^{(1-\frac{1}{4\ell})}} \), then
\[
|P(A) \cdot P(A)| \geq C’ q^3
\]
where
\[
P(A) = \left\{ \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \in SL_2(\mathbb{Z}_q) : a_{11} \in A \cap \mathbb{Z}_q^\times, a_{12}, a_{21} \in A \right\}.
\]

The proof relies on a result in \([4]\) previously established by D. Covert, A. Iosevich, and J. Pakianathan, which implies that if \( |A| \) is much larger than \( \sqrt{\ell} q^{(1-\frac{1}{4\ell})} \), then
\[
|\{(a_{11}, a_{12}, a_{21}, a_{22}) \in A \times A \times A \times A : a_{11} a_{22} + a_{12} a_{21} = t\}| = |A|^4 q^{-1} + \mathcal{R}(t)
\]
where \( |\mathcal{R}(t)| \leq \ell |A|^2 q^{(1-\frac{1}{2\ell})} \).

Martin Henk1, Eva Link1
1TECHNISCHE UNIVERSITÄT BERLIN, INSTITUT FÜR MATHEMATIK, SEKR. MA 4-1, STRASSE DES 17 JUNI 136, D-10623 BERLIN, GERMANY
Abstract:

By extending former results of Ehrhart, it was shown by Peter McMullen that the number of lattice points in the Minkowski-sum of dilated rational polytopes is a quasipolynomial function in the dilation factors. Here we take a closer look at the coefficients of these quasi-polynomials and show that they are piecewise polynomials themselves and that they are related to each other by a simple differential equation. As a corollary, we obtain a refinement of former results on lattice points in vector dilated polytopes

Guy Louchard1
1UNIVERSITÉ LIBRE DE BRUXELLES, BELGIUM, DÉPARTEMENT D’INFORMATIQUE, CP 212, BOULEVARD DU TRIOMPHE, B-1050 BRUXELLES, BELGIUM
Abstract:

Using the Saddle point method and multiseries expansions, we obtain from the generating function of the Eulerian numbers \( A_{n,k} \) and Cauchy’s integral formula, asymptotic results in non-central region. In the region \( k = n – n^\alpha \), \( 1 > \alpha > 1/2 \), we analyze the dependence of \( A_{n,k} \) on \(\alpha\). This paper fits within the framework of Analytic Combinatorics.

Zhiping Wang1, Xu Han1
1Department of Mathematics, Dalian Maritime University, 116026 Dalian, P.R. China
Abstract:

Given a distribution \(D\) of pebbles on the vertices of a graph \(G\), a pebbling move on \(G\) consists of removing two pebbles from a vertex and placing one on an adjacent vertex (the other is discarded). The pebbling number of \(G\), denoted \(f(G)\), is the smallest integer \(k\) such that any distribution of \(k\) pebbles on \(G\) allows one pebble to be moved to any specified vertex via pebbling moves. In this paper, we calculate the \(t\)-pebbling number of the graph \(D_{n,C_{2m}}\). Furthermore, we verify the \(q\)-\(t\)-pebbling number to demonstrate that \(D_{n,C_{2m}}\) possesses the \(2t\)-pebbling property.

Haixia Guo1,2, Jizhu Nan2
1College of Science, Tianjin University of Technology and Education, Tianjin, 300222, P, R. China
2School of Mathematica] Sciences, Dalian University of Technology, Dalian, 116024, P. R. China
Abstract:

Most. of pooling designs are always constructed by the “containment matrix”. But we are interested in considering non-containment
relationship. In [J. Guo, K. Wang, Pooling designs with surprisingly high degree of error correction in a finite vector space, Discrete Appl Math], Guo and Wang gave a construction by the use of non-containment relationship. In this paper, we generalize Guo-Wang’s designs and obtain a new family of pooling designs. Our designs and Guo-Wang’s designs have the same numbers of items and pools,but the error-tolerance property of our designs is better than that of Guo-Wang’s designs.

Mukund V.Bapat1, N.B. Limaye2
1Kelkar College of Arts and Science Devgad Maharashtra
2 Department of Mathematics LLT. Bombay Powai, Mumbai 400076
Abstract:

A \(k\)-edge labeling of a graph \(G\) is a function \(f: E(G) \to \{0, \ldots, k-1\}\). Such a labeling induces a labeling on the vertex set \(V(G)\) by defining \(f(v) := \sum f(e) \pmod{k}\), where the summation is taken over all edges \(e\) incident on \(v\). For an edge labeling \(f\), let \(v_f(i)\) (resp., \(e_f(i)\)) denote the number of vertices (resp., edges) receiving the label \(i\). A graph \(G\) is said to be \(E_k\)-cordial if there exists a \(k\)-edge labeling \(f\) of \(G\)such that \(|v_f(i) – v_f(j)| \leq 1\) and \(|e_f(i) – e_f(j)| \leq 1\) for all \(0 \leq i, j \leq k-1\). A wheel \(W_n\) is the join of the cycle \(C_n\) on \(n\) vertices and \(K_1\). A Helm \(H_n\) is obtained by attaching a pendent edge to each vertex of the cycle of the wheel \(W_n\). We prove that (i) Helms, (ii) one-point unions of helms, and (iii) path unions of helms are \(E_3\)-cordial.

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;