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 055
- Pages: 83-90
- Published: 30/11/2005
In this paper, we study the properties of super edge-magic total graphs. In particular, we propose some algorithms to construct new super edge-magic total graphs from the old ones. We also construct a super edge-magic total labeling on certain disconnected graphs, namely \( P_n \cup P_{n+1} \), \( nP_2 \cup P_n \), and \( nP_2 \cup P_{n+2} \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 71-82
- Published: 30/11/2005
Let \( G = G(v, e) \) be a finite simple graph with \( v \) vertices and \( e \) edges. An \((a, d)\)-\(\text{edge-antimagic-vertex}\) (EAV) \(\text{labeling}\) is a one-to-one mapping \( f: V(G) \to \{1, 2, \ldots, v\} \) such that for every edge \( xy \in E(G) \), the edge-weight set \(\{f(x) + f(y) \mid xy \in E(G)\} = \{a, a+d, a+2d, \ldots, a+(e-1)d\}\) for some positive integers \( a \) and \( d \). An \((a, d)\)-\(\text{edge-antimagic-total labeling}\) is a one-to-one mapping \( f: V(G) \cup E(G) \to \{1, 2, \ldots, v+e\} \) with the property that for every edge \( xy \in E(G) \),\(\{f(x) + f(y) + f(xy) \mid xy \in E(G)\} = \{a, a+d, a+2d, \ldots, a+(e-1)d\}.\) This labeling is called \(\text{super \((a, d)\)-edge-antimagic total labeling}\) if \( f(V(G)) = \{1, 2, \ldots, v\} \). In this paper, we investigate the relationship between the adjacency matrix, \((a, d)\)-edge-antimagic vertex labeling, and super \((a, d)\)-edge-antimagic total labeling, and show how to manipulate this matrix to construct new \((a, d)\)-edge-antimagic vertex labelings and new super \((a, d)\)-edge-antimagic total graphs.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 57-70
- Published: 30/11/2005
A total labeling of a graph \( G \) with \( p \) vertices and \( q \) edges is a one-to-one mapping from \( V(G) \cup E(G) \) onto \( \{1,2,\ldots,p+q\} \). If the edge-weights (resp. vertex-weights) form an arithmetic progression starting from \( a \) and having common difference \( d \), then the labeling is called an \( (a,d) \)-edge (resp. vertex) – antimagic total labeling. In this paper, we consider such labeling applied to the generalized Petersen graph.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 43-56
- Published: 30/11/2005
A simple graph \( G = (V,E) \) admits an \( H \)-\({covering}\) if every edge in \( E \) belongs to a subgraph of \( G \) isomorphic to \( H \). In this case, we say that \( G \) is \( H \)-\({magic}\) if there is a total labeling \( f : V \cup E \rightarrow \{1,2,\ldots,|V|+|E|\} \) such that for each subgraph \( H’ = (V’,E’) \) of \( G \) isomorphic to \( H \),\(\sum_{v \in V’} f(v) + \sum_{e \in E’} f(e)\)
is constant. When \( f(V) = \{1,\ldots,|V|\} \), we say that \( G \) is \( H \)-\({supermagic}\).We study \( H \)-magic graphs for several classes of connected graphs. We also provide constructions of infinite families of \( H \)-magic graphs for an arbitrary given graph \( H \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 33-42
- Published: 30/11/2005
Let \( \lambda \) be an edge-magic total (EMT) labeling of graph \( G(V, E) \). Let \( W \subset V(G) \cup E(G) \). Any restriction of \( \lambda \) to \( W \) is called a \({partial\; EMT \;labeling}\) on \( G \). A partial EMT labeling \( \pi \) is a critical set in \( \lambda \) if \( \lambda \) is the only edge-magic total labeling having \( \pi \) as its partial EMT labeling, and no proper restriction of \( \pi \) satisfies the first condition. In this paper, we study the property of critical sets in such a labeling. We determine critical sets in an EMT labeling for a given graph \( G \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 17-31
- Published: 30/11/2005
A \( (p,q) \) graph \( G \) is called edge-magic if there exists a bijective function \( f : V(G) \cup E(G) \rightarrow \{1,2,\ldots,p+q\} \) such that \( f(u) + f(v) + f(uv) \) is a constant for each edge \( uv \in E(G) \). Also, \( G \) is said to be super edge-magic if \( f(V(G)) = \{1,2,\ldots, p\} \). Furthermore, the super edge-magic deficiency, \( \mu_s(G) \), of a graph \( G \) is defined to be either 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 forests and 2-regular graphs is computed, which in turn leads to some conjectures on the super edge-magic deficiencies of graphs in these classes. Additionally, some edge-magic deficiency analogues to the super edge-magic deficiency results on forests are presented.
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 5-15
- Published: 30/11/2005
Suppose \( G = (V,E,F) \) is a finite plane graph with vertex set \( V(G) \), edge set \( E(G) \), and face set \( F(G) \). A bijection \( \lambda: V(G) \cup E(G) \cup F(G) \rightarrow \{1,2,3,\ldots,|V(G)| + |E(G)| + |F(G)|\} \) is called a labeling of type \( (1,1,1) \). The weight of a face under a labeling is the sum of the labels (if present) carried by that face and the edges and vertices surrounding it. A labeling of a plane graph \( G \) is called \( d \)-\({antimagic}\) if for every number \( s \geq 3 \), the set of \( s \)-sided face weights is\(W_s = \{a_s + id: 0 \leq i \leq f_s\}\) for some integers \( a_s \) and \( d \) (\( a > 0 \), \( d \geq 0 \)), where \( f_s \) is the number of \( s \)-sided faces. We allow different sets \( W_s \) for different \( s \).
In this paper, we deal with \( d \)-\({antimagic}\) labelings of type \( (1,1,1) \) for a special class of plane graphs \( C_a^b \) and we show that a \( C_a^b \) graph has \( d \)-antimagic labeling for \( d \in \{a-2,a-1,a+1,a+2\} \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 209-221
- Published: 30/11/2005
A \( V(m,t) \) leads to \( m \) idempotent pairwise orthogonal Latin squares of order \( (m+1)t+1 \) with one common hole of order \( t \). \( V(m,t) \)’s can also be used to construct perfect Mendelsohn designs and optimal optical orthogonal codes. For \( 3 \leq m \leq 8 \), the spectrum for \( V(m,t) \) has been determined. In this article, we investigate the existence of \( V(m,t) \) with \( m = 9 \) and show that a \( V(9,t) \) always exists in \( GF(q) \) for any prime power \( q = 9t + 1 \) with the exception of \( q = 73 \) and one possible exception of \( q = 5^6 \).
- Research article
- Full Text
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume 055
- Pages: 187-197
- Published: 30/11/2005
A Vertex Magic Total Labeling of a graph \( G \) is a one-to-one map \( \lambda \) from \( E(G) \cup V(G) \) onto the set of integers \( \{1, 2, \ldots, e + v\} \) such that for all \( x \in V \) we have \(\lambda(x) + \sum \lambda(xy) = h\) for some constant \( h \), where the sum is taken over all vertices \( y \) adjacent to \( x \). In this paper, we present several theorems on the existence of such labelings for multipartite graphs and give constructions for labelings for two infinite families of complete tripartite graphs, namely \( K_{1,n,n} \) for odd \( n \) and \( K_{2,n,n} \) for \( n \equiv 3 \pmod{4} \).
- Research article
- Full Text
- Ars Combinatoria
- Volume 077
- Pages: 311-318
- Published: 31/10/2005
In this paper, we develop a polynomial time algorithm to determine the cyclic edge connectivity of a \(k\)-regular graph for \(k \geq 3\). The time complexity of the algorithm is bounded by \(O(k^{11}|V|^8)\), in particular, it is \(O(|V|^8)\) for cubic graphs.




