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.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113-A
- Pages: 3-10
- Published: 31/01/2014
Let \(G\) be a graph, and let \(a\), \(b\), \(k\) be integers with \(0 \leq a \leq b\), \(k \geq 0\). An \([a, b]\)-factor of graph \(G\) is defined as a spanning subgraph \(F\) of \(G\) such that \(a \leq d_F(v) \leq b\) for each \(v \in V(F)\). Then a graph \(G\) is called an \((a, b, k)\)-critical graph if after deleting any \(k\) vertices of \(G\) the remaining graph of \(G\) has an \([a, b]\)-factor. In this paper, it is proved that, if \(a\), \(b\), \(k\) be integers with \(1 \leq a < b\), \(k \geq 0\) and \(b \geq a(k+1)\) and \(G\) is a graph with \(\delta(G) \geq a+k\) and binding number \(b(G) \geq a-1+\frac{a(k+1)}{b}\), then \(G\) is an \((a, b, k)\)-critical graph. Furthermore, it is shown that the result in this paper is best possible in some sense.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 473-476
- Published: 31/01/2014
Let \(R(a(x-y) = bz)\) denote the least integer \(n\) such that for every \(2\)-coloring of the set \(\{1, 2, \ldots, n\}\) there exists a monochromatic solution to \(a(x-y) = bz\). Recently, Gasarch, Moriarty, and Tumma conjectured that \(R(a(x-y) = bz) = b^2 + b + 1\), where \(1 < a < b\). In this note, we confirm this conjecture.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 463-471
- Published: 31/01/2014
In this paper, we introduce the notion of a generalized triple derivation \(f\), with an associated triple derivation \(d\), on a lattice and investigate some related results. Among some other results, we prove that: Let \((L, \wedge, \vee)\) be a distributive lattice and \(f\) be a generalized triple derivation, with associated triple derivation \(d\), on \(L\). Then the following conditions are equivalent for all \(x, y, z \in L\):
- \(f\) is an isotone generalized triple derivation on \(L\),
- \(f_{x \wedge y \wedge z} = f_x \wedge f_y \wedge f_z\),
- \(f_{x \vee y \vee z} = f_x \vee f_y \vee f_z\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 457-462
- Published: 31/01/2014
The scrambling index of an \(n \times n\) primitive matrix \(A\) is the smallest positive integer \(k\) such that \(A^k(A^T)^k > 0\), where \(A^T\) denotes the transpose of \(A\). In 2009, M. Akelbek and S. Kirkland gave an upper bound on the scrambling index of an \(n \times n\) primitive matrix \(M\) in terms of its order \(n\), and they also characterized the primitive matrices that achieve the upper bound. In this paper, we characterize primitive matrices which achieve the second largest scrambling index in terms of its order. Meanwhile, we show that there exists a gap in the scrambling index set of primitive matrices.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 451-455
- Published: 31/01/2014
Let \(d_G(v)\) be the degree of a vertex \(v\) in a graph \(G\). A graph \(G\) is called a \(D(i_1, \ldots,i_k)\) graph, if \(\{d_G(v) \mid x \in V(G)\} = \{i_1, \ldots, i_k\}\). In this paper, a necessary and sufficient condition for a connected \(D(1, 3)\) graph to be cordial is given.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 441-450
- Published: 31/01/2014
Let \(G\) be a connected graph of order \(n\), and suppose that \(n = \sum_{i=1}^{k}n_i\), where \(n_1, n_2, \ldots,n_n\) are integers with at least two. A spanning subgraph is called a path-factor if each component of it is a path of order at least two. In [Y. Chen, F. Tian, B, Wei, Degree sums and path-factors in graphs, Graphs and Combin. \(17 (2001),61-71.]\), Chen et al. gave a degree sum condition for the existence of a path-factor consisting of paths of order \(n_1, n_2, \ldots, n_k\). In this paper, for 2-connected graphs, we generalize this result.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 435-439
- Published: 31/01/2014
Let \(G\) be a graph with \(n\) vertices and \(\mu_1, \mu_2, \ldots, \mu_n\) be the Laplacian eigenvalues of \(G\). The Laplacian-energy-like graph invariant \(\text{LEL}(G) = \sum_{i=1}^{n} \sqrt{\mu_i}\) has been defined and investigated in [1]. Two non-isomorphic graphs \(G_1\) and \(G_2\) of the same order are said to be \(\text{LEL}\)-equienergetic if \(\text{LEL}(G_1) = \text{LEL}(G_2)\). In [2], three pairs of \(\text{LEL}\)-equienergetic non-cospectral connected graphs are given. It is also claimed that the \(\text{LEL}\)-equienergetic non-cospectral connected graphs are relatively rare. It is natural to consider the question: Whether the number of the \(\text{LEL}\)-equienergetic non-cospectral connected graphs is finite? The answer is negative, because we shall construct a pair of \(\text{LEL}\)-equienergetic non-cospectral connected graphs of order \(n\), for all \(n \geq 12\) in this paper.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 429-433
- Published: 31/01/2014
The status of a vertex \(v\) in a graph is the sum of the distances between \(v\) and all vertices. The status sequence of a graph is the list of the statuses of all vertices arranged in nondecreasing order. It is well known that non-isomorphic graphs may have the same status sequence. This paper gives a sufficient condition for a graph \(G\) with the property that there exists another graph \(G’\) such that \(G’\) and \(G\) have the same status sequence and \(G’\) is not isomorphic to \(G\).
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 415-428
- Published: 31/01/2014
We give combinatorial proofs of some binomial and $q$-binomial identities in the literature, such as
\[\sum\limits_{k={-\infty}}^{\infty}(-1)^kq^{\frac{(9k^2+3k)}{2}}\binom{2n}{n+3k}=(1+q^n)\prod\limits_{k=1}^{n-1}(1+q^k+q^{2k})(n\geq 1)\]
and
\[\sum\limits_{k=0}^{\infty} \binom{3n}{2k}(-3)^k=(-8)^n.\]
Two related conjectures are proposed at the end of this paper.
- Research article
- Full Text
- Ars Combinatoria
- Volume 113
- Pages: 405-414
- Published: 31/01/2014
In the spirit of Ryser’s theorem, we prove sufficient conditions on \(k\), \(\ell\), and \(m\) so that \(k \times \ell \times m\) Latin boxes, i.e., partial Latin cubes whose filled cells form a \(k \times \ell \times m\) rectangular box, can be extended to a \(k \times n \times m\) Latin box, and also to a \(k \times n \times m\) Latin box, where \(n\) is the number of symbols used, and likewise the order of the Latin cube. We also prove a partial Evans-type result for Latin cubes, namely that any partial Latin cube of order \(n\) with at most \(n-1\) filled cells is completable, given certain conditions on the spatial distribution of the filled cells.




