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
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 099
- Pages: 81-88
- Published: 30/11/2016
Multi-sender authentication codes allow a group of senders to construct an authenticated message for a receiver such that the receiver can verify the authenticity of the received message. In this paper, we construct one multi-sender authentication code from polynomials over finite fields. Some parameters and the probabilities of deceptions of this code are also compute
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 099
- Pages: 61-68
- Published: 30/11/2016
For graphs \(G\) and \(H\), Ramsey number \(R(G, H)\) is the smallest natural number \(n\) such that no \((G, H)\)-free graph on \(n\) vertices exists. In 1981, Burr [5] proved the general lower bound \(R(G, H) \geq (n – 1)(\chi(H) – 1) + \sigma(H)\), where \(G\) is a connected graph of order \(n\), \(\chi(H)\) denotes the chromatic number of \(H\) and \(\sigma(H)\) is its chromatic surplus, namely, the minimum cardinality of a color class taken over all proper colorings of \(H\) with \(\chi(H)\) colors. A connected graph \(G\) of order \(n\) is called good with respect to \(H\), \(H\)-good, if \(R(G, H) = (n – 1)(\chi(H) – 1) + \sigma(H)\). The notation \(tK_m\) represents a graph with \(t\) identical copies of complete graph \(K_m\). In this note, we discuss the goodness of cycle \(C_n\) with respect to \(tK_m\) for \(m, t \geq 2\) and sufficiently large \(n\). Furthermore, it is also provided the Ramsey number \(R(G, tK_m)\), where \(G\) is a disjoint union of cycles.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 099
- Pages: 69-79
- Published: 30/11/2016
If \(T\) is a tree on \(n\) vertices, \(n \geq 3\), and if \(G\) is a connected graph such that \(d(u) + d(v) + d(u,v) \geq 2n\) for every pair of distinct vertices of \(G\), it has been conjectured that \(G\) must have a non-separating copy of \(T\). In this note, we prove this result for the special case in which \(d(u) + d(v) + d(u,v) \geq 2n + 2\) for every pair of distinct vertices of \(G\), and improve this slightly for trees of diameter at least four and for some trees of diameter three.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 099
- Pages: 41-60
- Published: 30/11/2016
Let \(G\) be a finite simple group, \(M\) be a maximal subgroup of \(G\) and \(C_g = nX\) be the conjugacy class of \(G\) containing \(g\). In this paper we discuss a new method for constructing \(1-(v,k,\lambda)\) designs \(\mathcal{D} = (\mathcal{P},\mathcal{B})\), where \(\mathcal{P} = nX\) and \(\mathcal{B} = \{(M\cap nX)^y \mid y \in G\}\). The parameters \(v\), \(k\), \(\lambda\) and further properties of \(\mathcal{D}\) are determined. We also study codes associated with these designs.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 099
- Pages: 29-39
- Published: 30/11/2016
Let \(G\) be a graph and \(H\) a subgraph of \(G\). A \(D(G, H, \lambda)\) design is a collection \(\mathcal{D}\) of subgraphs of \(G\) each isomorphic to \(H\) so that every \(2\)-path (path of length \(2\)) in \(G\) lies in exactly \(\lambda\) subgraphs in \(\mathcal{D}\). The problem of constructing \(D(K_n,C_n,1)\) designs is the so-called Dudeney’s round table problem. We denote by \(C_k\), a cycle on \(k\) vertices and by \(P_k\), a path on \(k\) vertices.
In this paper, we construct \(D(K_{n,n},C_{2n},1)\) designs and \(D(K_n,P_n,1)\) designs when \(n \equiv 0,1,3 \pmod{4}\); and \(D(K_{n,n},C_{2n},2)\) designs and \(D(K_n,P_n,2)\) designs when \(n \equiv 2 \pmod{4}\). The existence problems of \(D(K_{n,n},C_{2n},1)\) designs and \(D(K_n,P_n,1)\) designs for \(n \equiv 2 \pmod{4}\) remain open.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 099
- Pages: 23-27
- Published: 30/11/2016
The spread of a graph \(G\) is defined as the difference between the largest and smallest eigenvalues of \(G\). Using the lower bounds obtained by Liu and Liu in [4] on the spread of a graph, we in this note present spread conditions for some Hamiltonian properties of a graph.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 099
- Pages: 3-21
- Published: 30/11/2016
A \({vertex \;cover}\) of a graph \(G = (V, E)\) is a subset \(S \subseteq V\) such that every edge is incident with at least one vertex in \(S\), and \(\alpha(G)\) is the cardinality of a smallest vertex cover. For a given vertex cover \(S\), a defense by \(S\) to an attack on an edge \(e = \{v, w\}\), where \(v \in S\), is a one-to-one function \(f : S \to V\), such that:
- \(f(v) = w\), and
- for each \(s \in S – v\), \(f(s) \in N[s]\).
Informally, a set is an \({eternal\; vertex \;cover}\) if it can defend an “attack” on any edge and the process can be repeated indefinitely. The cardinality of a smallest eternal vertex cover is denoted \(\alpha_{m}^\infty(G)\). A set of vertices which is not an eternal vertex cover is \({mortal}\). A formal definition of eternal vertex cover is provided and demonstrated to be equivalent to a characterization using closed families of vertex covers.
Eternal vertex covers are shown to be closed under taking supersets and a lower bound for \(\alpha_{m}^\infty(G)\) is given which depends on the vertex connectivity number and the independent domination number. A corresponding upper bound is given for the size of a mortal set. The \({death \;spiral\; number}\) of a mortal vertex cover is defined and used to partition the collection of all mortal sets. Mortal sets are shown to be closed under taking subsets implying the collection of mortal sets for a graph with at least one edge is an independence system. The death spiral number of a graph is the maximum of the death spiral numbers of all mortal sets.
An optimal attack/defense strategy is determined for a set of size \(\alpha_{m}^\infty(T) – 1\) in a tree \(T\), along with a polynomial labeling algorithm which computes its death spiral number.
- Research article
- Full Text
- Ars Combinatoria
- Volume 129
- Pages: 437-447
- Published: 31/10/2016
A graph \(G\) is called super edge-magic if there exists a bijective function \(f: V(G) \cup E(G) \rightarrow \{1, 2, \dots, |V(G)| + |E(G)|\}\) such that \(f(V(G)) = \{1, 2, \dots, |V(G)|\}\) and \(f(u) + f(v) + f(uv)\) is a constant for each \(uv \in E(G)\). The super edge-magic deficiency, \(\mu_s(G)\), of a graph \(G\) is defined as the smallest nonnegative integer \(n\) with the property that the graph \(G \cup nK_1\) is super edge-magic, or \(+\infty\) if there exists no such integer \(n\). In this paper, the super edge-magic deficiency of certain 2-regular graphs with two components is computed, which leads us to a conjecture on the super edge-magic deficiency of graphs in this class.
- Research article
- Full Text
- Ars Combinatoria
- Volume 129
- Pages: 417-436
- Published: 31/10/2016
From a computer search, new minimum sizes for the maximal partial spreads in \(PG(3,q)\) have been obtained for \(q = 8, 9, 16\) and for every \(q\) such that \(25 \leq q \leq 101\). Furthermore, density results in the cases \(q = 8, 9, 16, 19, 23, 25, 27\) have been obtained. Finally, the already known exceptional size \(45\) for \(q = 7\) has been found again.
- Research article
- Full Text
- Ars Combinatoria
- Volume 129
- Pages: 403-416
- Published: 31/10/2016
We decompose the complete multigraph \(K(v, \lambda)\) into copies of a graph \(H_i\) (\(i = 1, 2, 3\)). Each \(H_i\) is a near-triangle in that it is connected and has \(3\) vertices. In several cases, the decompositions are completed using classical combinatorial sequences due to Langford and Skolem.




