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.

Ewa M. Kubicka1, Kathleen A. McKeon2
1University of Louisville
2Connecticut College
Abstract:

An efficient method for generating level sequence representations of rooted trees in a well-defined order was developed by Beyer and Hedetniemi. In this paper, we extend Beyer and Hedetniemi’s approach to produce an algorithm for parallel generation of rooted trees. This is accomplished by defining the lexicographic distance between two rooted trees to be the number of rooted trees between them in the ordering of trees produced by the Beyer and Hedetniemi algorithm. Formulas are provided for the lexicographic distance between rooted trees with certain structures. In addition, we present algorithms for ranking and unranking rooted trees based on the ordering of the trees that is induced by the Beyer and Hedetniemi generation algorithm.

R. Balakrishnan1, T. Kavaskar1
1Srinivasa Ramanujan Centre, SASTRA University Kumbakonam-612 001, India.
Abstract:

A fall coloring of a graph \( G \) is a color partition of the vertex set of \( G \) in such a way that every vertex of \( G \) is a colorful vertex in \( G \) (that is, it has at least one neighbor in each of the other color classes). The fall coloring number \( \chi_f(G) \) of \( G \) is the minimum size of a fall color partition of \( G \) (when it exists). In this paper, we show that the Mycielskian \( \mu(G) \) of any graph \( G \) does not have a fall coloring and that the generalized Mycielskian \( \mu_m(G) \) of a graph \( G \) may or may not have a fall coloring. More specifically, we show that if \( G \) has a fall coloring, then \( \mu_{3m}(G) \) has also a fall coloring for \( m \geq 1 \), and that \( \chi_f(\mu_{3m}(G)) \leq \chi_f(G) + 1 \).

Abstract:

For a positive integer \( d \), a set \( S \) of positive integers is \({difference \; d -free}\) if \( |x – y| \neq d \) for all \( x, y \in S \). We consider the following Ramsey-theoretical question: Given \( d, k, r \in \mathbb{Z}^+ \), what is the smallest integer \( n \) such that every \( r \)-coloring of \( [1, n] \) contains a monochromatic \( k \)-element difference \( d \)-free set? We provide a formula for this \( n \). We then consider the more general problem where the monochromatic \( k \)-element set must avoid a given set of differences rather than just one difference.

Nozomu Ochiumi1, Fumiaki Kanazawa2, Masahiro Yanagidal1, Yasuichi Horibe1
1Department of Mathematical Information Science, Faculty of Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan
2Japan Patent Office, 3-4-3 Kasumigaseki, Chiyoda-ku, Tokyo 100-8915, Japan
Abstract:

The covering number for a subset of leaves in a finite rooted tree is defined as the number of subtrees which remain after deleting all the paths connecting the root and the other leaves. We find the formula for the total sum (hence the average) of the covering numbers for a given subset of labeled leaves over all unordered binary trees with \( n \) leaves.

Feng-Zhen Zhao1
1Department of Mathematics, Shanghai University, Shanghai 200444, China.
Abstract:

In this paper, we investigate properties of a new class of generalized Cauchy numbers. By using the method of coecient, we establish a series of identities involving generalized Cauchy numbers, which generalize some results for the Cauchy numbers. Furthermore, we give some asymptotic approximations of certain sums related to the generalized Cauchy numbers.

Alexander Raichev 1, Mark C. Wilson 1
1Department of Computer Science University of Auckland Private Bag 92019, Auckland, New Zealand
Abstract:

Let \( F(x) = \sum_{\nu \in \mathbb{N}^d} F_\nu x^\nu \) be a multivariate power series with complex coefficients that converges in a neighborhood of the origin. Assume \( F = G / H \) for some functions \( G \) and \( H \) holomorphic in a neighborhood of the origin. We derive asymptotics for the coefficients \( F_{r\alpha} \) as \( r \to \infty \) with \( r\alpha \in \mathbb{N}^d \) for \( \alpha \) in a permissible subset of \( d \)-tuples of positive reals. More specifically, we give an algorithm for computing arbitrary terms of the asymptotic expansion for \( F_{r\alpha} \) when the asymptotics are controlled by a transverse multiple point of the analytic variety \( H = 0 \). This improves upon earlier work by R. Pemantle and M. C. Wilson. We have implemented our algorithm in Sage and apply it to obtain accurate numerical results for several rational combinatorial generating functions.

Toufik Mansour 1, Mark Shattuck 2
1Mathematics Department University of Haifa Haifa, Israel 31905
2Mathematics Department University of Tennessee Knoxville, TN 37996
Abstract:

Let \( P(n, k) \) denote the set of partitions of \( [n] = \{1, 2, \ldots, n\} \) containing exactly \( k \) blocks. Given a partition \( \Pi = B_1 / B_2 / \cdots / B_k \in P(n, k) \) in which the blocks are listed in increasing order of their least elements, let \( \pi = \pi_1 \pi_2 \cdots \pi_n \) denote the canonical sequential form wherein \( j \in B_{\pi_j} \) for all \( j \in [n] \). In this paper, we supply an explicit formula for the generating function which counts the elements of \( P(n, k) \) according to the number of strings \( k1 \) and \( r(r+1) \), taken jointly, occurring in the corresponding canonical sequential forms. A comparable formula for the statistics on \( P(n, k) \) recording the number of strings \( 1k \) and \( r(r-1) \) is also given, which may be extended to strings \( r(r-1) \cdots (r-m) \) of arbitrary length using linear algebra. In addition, we supply algebraic and combinatorial proofs of explicit formulas for the total number of occurrences of \( k1 \) and \( r(r+1) \) within all the members of \( P(n, k) \).

Luca S. Ferrari 1
1Dipartimento di Matematica, Universit`a di Bologna Piazza di Porta San Donato, 5 – 40126 Bologna, Italy
Abstract:

A word is centrosymmetric if it is invariant under the reverse-complement map. In this paper, we give  enumerative results on k-ary centrosymmetric words of length n avoiding a pattern of length 3 with no repeated letters.

Timothy DeVries 1, Joris van der Hoeven 2, Robin Pemantle 1
1Department of Mathematics, University of Pennsylvania 209 South 33rd Street, Philadelphia, PA 19104
2CNRS, Laboratoire LIX, Ecole Polytechnique ´ F-91228 Palaiseau Cedex, France
Abstract:

We consider a bivariate rational generating function
\[
F(x, y) = \frac{P(x, y)}{Q(x, y)} = \sum_{r, s \geq 0} a_{r,s} x^r y^s
\]
under the assumption that the complex algebraic curve \( \mathcal{V} \) on which \( Q \) vanishes is smooth. Formulae for the asymptotics of the coefficients \( \{a_{r,s}\} \) are derived in [PW02]. These formulae are in terms of algebraic and topological invariants of \( \mathcal{V} \), but up to now these invariants could be computed only under a minimality hypothesis, namely that the dominant saddle must lie on the boundary of the domain of convergence. In the present paper, we give an effective method for computing the topological invariants, and hence the asymptotics of {\(a_{rs}\)}, without the minimality assumption. This leads to a theoretically rigorous algorithm, whose implementation is in progress at http://www.mathemagix.org

V. Abatangelo1, B. Larato1
1Dipartimento di Matematica Politecnico di Bari, Via Orabona 4, 1-70125 Bari, Italy,
Abstract:

A complete arc of size \(q^2 – 1\) is constructed in the Moulton plane of order \(q^2\) for \(q \geq 5\) odd.

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;