A vertex \(v\) is called an AR-vertex, if \(v\) has distinct sum of edge labels for each distinct subset of edges incident on \(v\). i.e., if \(\{x_1,x_2,\dots,x_k\}\) are the edge labels of the edges incident on \(v\), then the \(2^k\) subset sums are all distinct. An injective edge labeling \(f\) of a graph \(G\) is said to be an AR-labeling of \(G\) if \(f:E \rightarrow \mathbb{N}\) is such that every vertex in \(G\) is an AR-vertex under \(f\). A graph \(G\) is said to be an AR-graph if there exists an AR-labeling \(f:E\rightarrow \{1,2,\dots,m\}\), where \(m\) denotes the number of edges of \(G\). A study of AR-labeling and AR-graphs is initiated in this paper.
The Ramsey theory is a branch of combinatorics exploring the presence of order in every given structure man constructs. Philosophically speaking, the Ramsey Theory states that there cannot be absolute chaos in any system. A precursor to this idea can be found in Schur’s Theorem [11] by Issai Schur which states that, if the set of positive integers \(\mathbb{N}\) is finitely colored, then there exist \(x,y\) and \(z\) of the same color such that \(x+y=z.\)
Richard Rado, a student of Schur, proved that the equation \(c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}=0\) is partition regular (i.e., it has a monochromatic solution whenever \(\mathbb{N}\) is finitely colored) if and only if there is \(J\subseteq [n]\) (where \([n]\) denotes \(\{1,2,3,\dots,n\}\)) such that \(\sum\limits_{i \in J} c_{i}=0\). Schur’s Theorem can be identified as a particular case of Rado’s theorem with coefficients of \(x_{1}, x_{2}\) and \(x_{3}\) being 1, 1 and -1 respectively. Rado’s theorem is considered a part of the Ramsey theory since it guarantees that, for any linear equation satisfying the regularity condition, every \(r\)-coloring of a sufficiently large initial segment of natural numbers contains a monochromatic solution. Thus, the regularity condition imposed by Rado on the linear equation is essential and cannot be compromised.
Motivated by the strength of this condition, if we introduce a similar line of restriction on the vertices in an edge labeled graph, soon we realize that the number-theoretic notion of regularity slowly disappears while using sufficiently large natural numbers. In other words, given any graph, we can label its edges with natural numbers (sufficiently large) so that the number-theoretic notion of regularity is absent from every vertex of the graph. In fact, given a graph \(G\), if we restrict our labeling to a one-one function from the edge set \(E(G)\) of the graph \(G\) to \(\mathbb{N}\), vertices with degree at most 2 will never be number-theoretically regular. So we asked the question whether we can label the edges of a graph in such a way that the set of edge labels incident on any given vertex has distinct subset sums. In other words, in terms of Rado’s partition regularity, can we label edges so that among the labels of edges incident on any vertex, there exists no linear combination of them (with coefficients \(\pm 1\)) summing to 0? In this paper, we formulate this question as an edge labeling problem in graphs which we call AR-labeling1.
Graph labeling is a lucid but impactful tool, good enough to simplify complicated human work in very many real-life situations. A labeled graph works as a frame of reference by being a typical model for some specific application purpose worthy of analysis in its own regard. A graph labeling technique is basically an assignment of some particular labels to either vertices or edges or both of a graph, requiring some condition to be fulfilled. This approach was initially introduced in the mid-1960s, but in the six decades that have passed, around 3000 research articles have been published based on different graph labeling assignments [4]. Even though the number of vertex labeling assignments are considerably more than their edge counterparts, there have been some very important edge labeling techniques, well renowned for their diverse applications in solving real-world problems. Edge-graceful labeling [13] and Harmonious labeling [5] stand out in this regard with a remarkable number of follow up works based on both theoretical advancement and practical application. Prime labeling [15], Leech labeling [12], Magic labeling [10] and Anti-magic labeling [6] have also created substantial interest and curiosity among researchers around the world. Sets with distinct subset sum property have seldom appeared in graph labeling. In fact, the edge labeling proposed in this paper – apart from being a labeling technique with its own applications – serves as a pioneer to many edge labeling assignments insisting on some specific number theoretic restrictions on the sets of labels it creates.
By a graph \(G=(V,E)\) we mean a finite simple undirected graph. The order \(\left|V\right|\) and the size \(\left|E\right|\) of \(G\) are denoted by \(n\) and \(m\), respectively. For all graph theoretic terminology and notations not mentioned here, we refer to Balakrishnan and Ranganathan [1].
Definition 1.1. Let \(f: E \rightarrow \mathbb{N}\) be an injective edge labeling of a graph \(G\). A vertex \(v\) is called an AR-vertex, if \(v\) has distinct sum of edge labels for each distinct subset of edges incident on \(v\). i.e., if \(\{x_1,x_2,\dots,x_k\}\) is the set of labels of edges incident on \(v\), then the \(2^k\) subset sums are all distinct.
Definition 1.2. An injective edge labeling \(f\) of a graph \(G\) is said to be an AR-labeling of \(G\), if \(f:E \rightarrow \mathbb{N}\) is such that every vertex in \(G\) is an AR-vertex under \(f\).
Definition 1.3. A graph \(G\) is said to be an AR-graph, if there exists an AR-labeling \(f:E \rightarrow \{1,2,\dots,m\}\), where \(m\) denotes the number of edges of \(G\).
Figure 1 illustrates AR-labeling of the Petersen graph.
AR-labeling of a graph \(G\) makes each subset of edges incident on every vertex \(v\) unique to the point of identifying them using an ordered pair \((v, k)\), where \(k \in \mathbb{N}\). In an information-theoretic interpretation [3], namely in the setting of signaling over a multiple access channel, we can interpret the integers as pulse amplitudes that \(n\) transmitters can transmit over an additive channel to send one bit of information each, for example, to signal to the base station that they want to start a communication session. The requirement that all subset sums be distinct expresses the desire that the base station be able to infer any possible subset of active users.
In this section, we prove a set of lemmas regarding AR-vertices which will be used to prove theorems in the later sections. We believe that these lemmas will be extremely useful for those who wish to work in this concept.
Lemma 2.1. The vertices of \(G\) with degree less than or equal to 2 are AR-vertices in every injective edge labeling of \(G\).
Proof. If \(v\) is a vertex of degree one, there is only one edge incident on \(v\) and hence only one number appears as a sum of edge labels.
If \(v\) is a vertex of degree 2. Consider an injective edge labeling of \(G\). Suppose \(v\) is adjacent to two edges say \(e_{1}\) and \(e_{2}\). Let \(e_{1}\) and \(e_{2}\) be labeled \(x\) and \(y\) respectively. Due to the injectivity of the labeling, \(x\neq y\), and since the labels are from positive integers, \(x+y\) cannot be equal to either \(x\) or \(y\). Hence, in both scenarios, \(v\) is an AR-vertex. \(\square\)
Lemma 2.2. A vertex of degree 3 can be made an AR-vertex by labeling the edges incident on \(v\) using distinct odd numbers.
Proof. Let \(x, y\) and \(z\) be three distinct odd numbers. The sum of every pair will be an even number, which would not be equal to the third number. And the sum of all three would be greater than every number as well as each pair-wise sum. \(\square\)
Lemma 2.3. Given a vertex \(v\) in G, if any two edges incident on \(v\) are labeled \(x\) and \(y\), then a third edge can be \(z\) if and only if \(x + y \neq z\) and \(|x – y| \neq z\). Moreover, if the edges incident on a vertex \(v\) of degree three are labeled \(x\), \(y\) and \(z\) with \(x<y<z\), then \(v\) is an AR-vertex if \(x + y \neq z\).
Proof. The pair-wise sums including \(z\) will always be greater than singletons. \(\square\)
Lemma 2.4. If the edges incident on a vertex \(v\) with degree three are labeled with numbers in arithmetic progression having common difference \(d\), then \(v\) is an AR-vertex if the least element \(x\) among the edge labels is not \(d\), that is \(x \neq d\).
Proof. By Lemma 2.3, \(v\) is an AR-vertex if and only if \(2x+d \neq x+2d\). \(\square\)
Lemma 2.5. Given 8 vertices labeled with some numbers with each number appearing at most twice, and given 4 distinct numbers \(x_1\), \(x_2\), \(x_3\) and \(x_4\), we can always label any set of 4 independent edges between these vertices, using \(x_1\), \(x_2\), \(x_3\) and \(x_4\), with the edge labels being distinct from the label of the vertices it is incident on.
Proof. Let \(e_1,e_2,e_3\) and \(e_4\) be the independent edges and for \(i \in [4]\), let \(y_i\) and \(y_i’\) be the labels given to the end vertices of \(e_i\). Let \(X = \{x_i: i \in [4]\}\) and let \(S_i = X \setminus \{y_i,y_i’\}\). If \(S_i = S_j\), for some \(i \neq j \in [4]\), then without loss of generality we may assume that \(i = 1\) and \(j=2\). Note that, in this case \(y_1 \neq y_1’\) and \(y_2 \neq y_2’\), so that cardinality of \(S_1\) (equivalently, \(S_2\)) is 2. Therefore, let \(S_1 = S_2 = \{x_a,x_b\}\), so that \(\{y_i,y_i’\} = \{x_c,x_d\}\), for \(i=1,2\), where \(\{a,b,c,d\} = [4]\). Note that \(x_c\) and \(x_d\) cannot be used to label any further vertex as both of them are already used twice. In this case assign \(x_a\) and \(x_b\) to \(e_1\) and \(e_2\) and \(x_c\) and \(x_d\) to \(e_3\) and \(e_4\), in some order and we are done.
Now assume that \(S_i\)’s are all different for different \(i\)’s. Let \(x_a \in S_1\) and assign it to the edge \(e_1\). Note that \(S_2\) contains at least two elements and at least one of them must be different from \(x_a\), say \(x_b\). Assign \(x_b\) to the edge \(e_2\). Again, \(S_3\) must be different from \(S_2\). Therefore, \(S_3\) contains an element \(x_c\) different from \(x_a\) and \(x_b\) or \(S_3 = \{x_a,x_b\}\) and \(S_2\) contains an element \(x_c\) different from \(x_a\) and \(x_b\). In the first case assign \(x_c\) to \(e_3\) and in the second case assign \(x_c\) to \(e_2\) and \(x_b\) to \(e_3\). Now, if \(x_d \in S_4\), then assign \(x_d\) to \(e_4\) and else, \(x_d\) must be present in at least two of the sets \(S_i\) and \(S_j\), \(i \neq j \in [3]\). In this case, \(S_i\) contains the label given to \(e_i\) and \(S_j\) contains the label given to \(e_j\), and at least one among them must be present in \(S_4\). Without lose of generality, let \(x_i \in S_4\). Assign that label \(x_i\), where \(i \in \{a,b,c\}\) to \(e_4\) and assign \(x_d\) to the edge which was assigned \(x_i\) and we are done.
Hence, the lemma follows. \(\square\)
Note that a statement similar to that of Lemma 2.5 is not true when we have 3 different numbers and 6 labeled vertices with each label appearing at most twice. For instance, let \(v_1,v_2,v_3,v_4,v_5,v_6\) be the vertices which are assigned labels 1, 1, 2, 3, 2, 3 and let \(v_1v_2, v_3v_4, v_5v_6\) be the independent edges. We cannot simultaneously assign two distinct values to \(v_3v_4\) and \(v_5v_6\). But, Lemma 2.5 can be easily extended to the following observation.
Observation 2.6. If we have \(k\) distinct numbers \((k\geq 4)\) and \(2k\) labeled vertices with each label appearing at most twice, we can always label any set of \(k\) independent edges between these vertices with the edge labels being distinct from the label of the vertices it is incident on.
Proof. Let \(e_1,e_2,\ldots,e_k\) be the independent edges with labels \(y_i\) and \(y_i’\) assigned to the end vertices of \(e_i\), for \(i \in [k]\). Let \(X = x_1,x_2,\ldots, x_k\) be the given \(k\) distinct numbers. Here, to label \(e_1\) we have at least \(k-2\) elements in \(X\) different from \(y_1\) and \(y_1’\) and we can arbitrarily choose one element from this to label \(e_1\), say \(x_1’\). (Note that \(x_1′ = x_j\) for some \(j \in [k]\)). Now, to label \(e_2\) we have at least \(k-3\) elements in \(X \setminus \{x_1’\}\) different from \(y_2\) and \(y_2’\) and we can arbitrarily choose one element from this to label \(e_2\), say \(x_2’\). Proceeding like this, we have at least \(k-i-1\) elements in \(X \setminus \{x_1′,x_2′,\ldots,x_{i-1}’\}\) different from \(y_i\) and \(y_i’\) and we can arbitrarily choose one element from this to label \(e_i\), say \(x_i’\). We can repeat this procedure up to \(i = k – 4\) and then apply Lemma 2.5 to complete the proof of the observation. \(\square\)
Lemma 2.7. Let \(\{a_1, a_2, a_3, a_4\}\) be a set having distinct subset sums with \(a_i < a_j\) for \(i < j\), then for every \(k \geq a_4, \{k+a_1, k+a_2, k+a_3, k+a_4\}\) is also having distinct subset sums.
Proof. Since \(\{a_1, a_2, a_3, a_4\}\) has 4 distinct elements, so has \(\{k+a_1, k+a_2, k+a_3, k+a_4\}\). Now assume that there exists a two-element set with subset sum equaling another two-element set. Because of the ascending order of the elements, this could happen only if \(k+a_1 + k+a_4 = k+a_2 + k+a_3\), but this would imply \(a_1 + a_4 = a_2 + a_3\) which contradicts the fact that \(\{a_1, a_2, a_3, a_4\}\) is a set with distinct subset sums. Hence our assumption is wrong. Suppose, if possible, let’s assume that the sum of a two-element or three-element subset equals another element, say \(k + a_i\) for some \(i\). But this implies \(a_i > k\) which is a contradiction to our choice of \(k\). Hence the lemma. \(\square\)
Lemma 2.8. If \(\{a_1, a_2,\ldots, a_j\}\) is the set of edge labels incident on an AR-vertex with all elements even, then any vertex with degree \((j+1)\) and the set of edge labels incident being \(\{a_1, a_2, \ldots, a_j, b\}\) is an AR-vertex if \(b\) is an odd number.
Proof. No linear combination of the first \(j\) labels (with coefficients \(0, \pm 1\)) yields an odd sum. Every linear combination containing the edge label \(b\) can be formed only by including \(b\). Hence the lemma. \(\square\)
Lemma 2.9. Let \(\{a_1, a_2, a_3\}\) be a set with distinct subset sums with \(a_i < a_j\) for \(i < j\), \(\{a_1, a_2, a_3, a_4\}\) is a set with distinct subset sums except for at most 10 values of \(a_4\) provided \(a_4 \notin \{a_1, a_2, a_3\}\).
Proof. If \(\{a_1, a_2, a_3\}\) has distinct subset sums and \(a_4 \neq a_i\) for \(i = 1,2,3\), then \(\{a_1, a_2, a_3, a_4\}\) will have two distinct subsets with same subset sum if and only if \(a_4 \in \{a_2 – a_1, a_3 – a_2, a_3 – a_1, |a_3 – (a_1 + a_2)|, a_3 + a_1 – a_2, a_3 + a_2 – a_1, a_1 + a_2, a_1 + a_3, a_2 + a_3, a_1 + a_2 + a_3 \}\). Hence the lemma. \(\square\)
Observation 2.10. From Lemma 2.9, if \(\{a_1, a_2, a_3\}\) is the set of distinct odd numbers and \(c\) is an even number greater than all three, then any vertex with a set of edge labels incident being \(\{a_1, a_2, a_3, c\}\) is an AR-vertex if no pair of the initial three labels sum to \(c\).
Proof. Two element sets with \(c\) form an odd number which cannot be equal to any singleton. The three-element sum of the first three numbers is odd. Hence the lemma. \(\square\)
Observation 2.11. From Lemma 2.9, if \(\{a_1, a_2, a_3\}\) is a set of distinct odd numbers with \(a_1 < a_2 < a_3\) and \(a_4\) is another odd number with \(a_4 > a_3\), then a vertex with edge labels incident being \(\{a_1, a_2, a_3, a_4\}\) will be an AR-vertex if \(a_1 + a_2 + a_3 \neq a_4\) and \(a_1 + a_4 \neq a_2 + a_3\).
Proof. An odd sum could repeat only when the sum of a three-element set equals the singleton. Two-element sums could be equal only one way because of the restriction imposed by the ascending order of elements. \(\square\)
Observation 2.12. From Lemma 2.9, if \(a_1, a_2\) and \(a_3\) are in arithmetic progression with common difference \(d\) with \(a_1 > d\), then a vertex with edge labels incident being \(\{a_1, a_2, a_3, a_4\}\), \(a_4 \notin \{a_1, a_2, a_3\}\), is an AR-vertex if \(a_4 \notin \{d, 2d, a_1 – d, a_3 + d, a_1 + a_2, a_1 + a_3, a_2 + a_3, a_1 + a_2 + a_3\}\).
Proof. The set actually exhausts all possible scenarios where the new number could create two distinct subsets with the same subset sum. \(\square\)
Lemma 2.13. If \(\{a_1, a_2, \ldots, a_j\}\) is the set of edge labels incident on an AR-vertex, then any vertex with degree \((j+1)\) and the set of edge labels incident being \(\{a_1, a_2,\ldots, a_j, b\}\) is an AR-vertex if \(b > a_1 + a_2 + a_3 +\ldots+ a_j\).
Proof. The largest number appearing as a linear combination (with coefficients \(0,\pm 1\)) of the first \(j\) edge labels is the sum of all \(j\) labels which is less than \(b\) by choice. Every subset sum containing the edge label \(b\) will be greater than \(b\). Hence the lemma. \(\square\)
Whenever a new labeling is introduced, identifying graph classes which satisfy such a labeling is an important question to be addressed. One should keep in mind that there are graph labelings like Leech labeling [12] which was initially defined in 1975 only for trees and till date there are only five known Leech trees. Still its extension to the class of all graphs provides infinite family of Leech graphs [16]. In this section, we provide some infinite families of graphs which are AR-graphs.
(1) Paths and cycles. For every injective edge labeling of G, Lemma 2.1 assures vertices of a path or cycle are AR. Let the edges be labeled from 1 to \(m\) in any order, paths and cycles are AR-graphs.
(2) Attaching a path to a cycle. The only vertex that raises a concern would be the vertex where path is connected to the cycle. Let \(v\) be that vertex. Since \(v\) has degree 3, \(v\) is not trivially AR. Also, the smallest such graph has 4 edges. Label the edges incident on \(v\) as 1, 2 and 4 and label the remaining edges using \(\{3, 5,6,7,\dots, m\}\). \(G\) will be AR under this labeling which is from \(E\rightarrow\{1,2,3,\dots, m\}\). Hence \(G\) is an AR-graph.
(3) Attaching a path to a pendant vertex in an AR-graph. Direct consequence of Lemma 2.1 and the fact that the initial graph is an AR-graph.
(4) Attaching a path of length at least \(2\) to a degree \(2\) vertex in an AR-graph. Since the initial graph \(G\) has an AR-labeling \(f:E\rightarrow \{1,2,3,\dots,m(G)\}\) and the path to be attached has at least two edges, we can use edge labels \(m+1\) and \(m+2\) while labeling the new graph. Let \(v\) be the vertex on which the new path is attached. Keeping the edge labels of \(G\) from \(f\), let the label of the two edges in \(G\) incident on \(v\) be some \(x\) and \(y\). Label the third edge incident on \(v\) as \(m+1\) if \(x+y\neq m+1\), otherwise label the edge as \(m+2\). By Lemma 2.3, \(v\) is an AR-vertex. Hence the result.
(5) Attaching a path to every vertex of a cycle. Let \(C_{n_1}\) be the cycle with \(n_1\) vertices. Let \(G\) be a graph formed by attaching paths to all vertices of \(G\). Suppose \(m\geq 4{n_1} – 1\). Label all the edges incident on the vertices of the cycle using consecutive odd numbers starting from 1. By Lemma 2.2, every vertex on the cycle will be AR-vertices. Use the labels \(\{2,4,6,\dots, 4{n_1}-2, 4{n_1}, 4{n_1}+2, \ldots, m\}\) on the remaining edges. By Lemma 2.1, vertices not on the cycle are also AR-vertices. Since this AR-labeling is from \(E \rightarrow \{1,2,3,\dots, m\}\), \(G\) is an AR-graph.
Suppose \(m \leq 4{n_1}-2\). Let the cycle be \(v_{1}v_{2}v_{3}\dots v_{n_1}\). Label the edges on the cycle using 1 to \(n_1\) (\(v_1 v_2\) as 1, \(v_2 v_3\) as 2, \(\dots\), \(v_{n_1} v_1\) as \(n_1\)). Now, label the edges not in the cycle but incident on its vertices as follows. Label the edge incident on \(v_i\) as \(n_1 + i – 1\) for \(i = 2,3,4, \dots n_1-1\), the edge incident on \(v_{n_1}\) as \(2n_1\) and the edge incident on \(v_1\) as \(2n_1-1\). Label the remaining edges using numbers less than or equal to \(m\), and not yet used in the labeling.
The labels of edges incident on vertex \(v_k\) on the cycle are \(k – 1, k\) and \(n_1 + k – 1\) if \(1 < k < n_1\). \(n_1 -\)1, \(n_1\) and \(2n_1\) are the labels of edges incident on \(v_{n_1}\). 1, \(n_1\) and \(2n_1\) are the labels of edges incident on \(v_1\). Due to Lemma 2.1, the vertices not in the cycle are trivially AR-vertices. By Lemma 2.3, the vertex \(v_k\) on the cycle is AR since \(k-1 + k \neq n_1 + k -1\), if \(k < n_1\) and \(v_1\) is \(AR\) since \(n_1 + 1 \neq 2n_1\), as a cycle has more than two vertices. And \(v_{n_1}\) is an AR-vertex since \(n_1 – 1 + n_1 \neq 2n_1\). So, attaching a path to every vertex of a cycle results in an AR-graph.
Figure 2 illustrates the AR-labeling of attaching a path of length 1 to every vertex of a cycle \(C_n\). Using Lemma 2.1, this labeling can be extended to a graph obtained by attaching a path of arbitrary length to every vertex of \(C_n\).
(6) The Cartesian product of cycles with \(K_2\), \(C_n \square K_2\). We have two copies of the same cycle with \(n\) vertices and each vertex in a cycle is adjacent to the corresponding vertex in the other cycle.
So if \(v_1 v_2 v_3 \dots v_n v_1\) is the first cycle and \(u_1 u_2 u_3 \dots u_n u_1\) is the second cycle, the additional edges would be \(v_1 u_1 , v_2 u_2, \dots , v_n u_n\).
Consider the labeling \(f\), \(f(v_iv_{i+1}) = i, f(u_iu_{i+1}) = n+i\) for \(1\leq i \leq n-1\), \(f(v_nv_{1}) = n, f(u_nu_{1}) = 2n\) and \(f(u_iv_i) = 2n+i\) for every \(i\).
It is easy to verify that \(f\) is an AR-labeling of \(C_n \square K_2\), which makes it an AR-graph. In fact, we have a stronger result that every Hamiltonian cubic graph is an AR-graph.
A cubic graph is a 3-regular graph, that is, a graph in which the degree of each vertex is 3. Hence a cubic graph \(G\) on \(n\) vertices has \(\frac{3n}{2}\) edges. Moreover, labeling each edge of \(G\) using an odd number, we get an AR-labeling of \(G\) by Lemma 2.2. So, there exists an AR-labeling \(f:E(G)\rightarrow \{1,2,3,\dots,3n-1\}\). Also if \(G\) is cubic, then \(G\) has even number of vertices. That is, \(n = 2k\) for some \(k \in \mathbb{N}\). \(K_4\) is the cubic graph on 4 vertices and the labeling in Figure 3 shows that \(K_4\) is an AR-graph.
There are exactly 2 cubic graphs on 6 vertices, one is edge-transitive and the other is not. Figure 4 shows that both these cubic graphs are AR-graphs.
Theorem 4.1. All Hamiltonian cubic graphs are AR-graphs.
Proof. Let \(G\) be a cubic graph with more than 6 vertices (since 4 and 6 are settled). For a cubic graph with \(n = 2k\) vertices, there will be \(3k\) edges. Being Hamiltonian, there exists a cycle \(C_n\) in \(G\) which includes all the vertices of \(G\). Let the cycle \(C_n\) be \(v_1 v_2 v_3 \dots v_n v_1\). Label the edges of the cycle from 1 to \(n\), \(v_1 v_2\) as 1, \(v_2 v_3\) as 2, \(\dots\), \(v_j v_{j+1}\) as \(j\), \(\dots\), \(v_{n-1} v_n\) as \(n-1\) and \(v_n v_1\) as \(n\). Now we have to label the remaining edges using numbers \(n+1, n+2,\dots, n + k\). Since we have labeled edges continuously using consecutive natural numbers, the only sum that repeats would be \(n+1\) which appears as the sum of edge labels for \(v_1\) as well as \(v_{k+1}\).
For each vertex \(u\) in G, consider the sum of labels of edges incident on \(u\) as a label. So now we have \(k\) distinct numbers and \(2k\) vertices labeled with only one label repeating exactly once. Since \(G\) has more than 6 vertices, we have \(k \geq 4\). Applying Observation 2.6, there exists an AR-labeling of \(G\) (Edge labels given are distinct from the sum of labels of edges already incident on those vertices). Since we have used only numbers from 1 to \(3k\), \(G\) is an AR-graph. \(\square\)
Theorem 4.2. Cubic graphs whose vertex set could be expressed as a disjoint union of vertex sets of cycles in the graph are AR-graphs.
Proof. Let \(G\) be a cubic graph whose vertex set could be written as a disjoint union of vertex sets of cycles in \(G\). Let \(C^1 , C^2 , \dots , C^b\) be the \(b\) disjoint cycles. Let cycle \(C^i\) has \(a_i\) vertices, then the disjoint cycles are of the form \(C_{a_1}\), \(C_{a_2}\), \(\dots\), \(C_{a_b}\). Clearly, \(\sum\limits_{i=1}^{b} a_i = n\). Now label the edges in \(C_{a_1}\) from 1 to \(a_1\), edges in \(C_{a_2}\) from \(a_1 + 1\) to \(a_1 + a_2\), edges in \(C_{a_3}\) from \(a_1 + a_2 + 1\) to \(a_1 + a_2 +a_3\), proceeding this way, edges in \(C_{a_j}\) from \(1 + \sum\limits_{i=1}^{j-1} a_i\) to \(\sum\limits_{i=1}^{j} a_i\), eventually edges in \(C_{a_b}\) from \(1+\sum\limits_{i=1}^{b-1} a_i\) to \(\sum\limits_{i=1}^{b} a_i = n\).
We have to label the remaining \(k = \frac{n}{2}\) edges using numbers from \(n+1\) to \(n+k\). Since cubic graphs with at most 6 vertices are AR graphs, let us consider only those graphs having more than 6 vertices.
Since we have labeled edges continuously till this point, after having labeled \(n\) edges, a number appears as the sum of edge labels in exactly one cycle and at most twice. Since there are at least 8 distinct vertices and \(G\) is satisfying the condition of Observation 2.6, we conclude that there exists a labeling of those \(k\) edges that results in an AR-labeling of \(G\) from \(E(G)\) to \(\{1,2, \ldots,3k\}\), hence \(G\) is an AR-graph. \(\square\)
Corollary 4.3. A graph \(G\) with \(\Delta(G) \leq 3\), whose vertex set could be partitioned into vertex sets of cycles of \(G\) is an AR-graph.
Proof. Since \(C_3, C_4\), \(K_4 – e\) and \(K_4\) are AR-graphs (AR-labeling of \(K_4 – e\) can be deduced from Figure 3), we need to consider only graphs with \(n>4\). The labeling technique follows from the theorem. Label all the edges in the cycles using consecutive natural numbers starting from 1. While labeling the remaining edges, if there are at least four of them, the corollary follows from Observation 2.6. Assume \(m \leq n+3\). Under the purview of this corollary, \(m=n\) implies a cycle which is an AR-graph. Suppose \(m = n+1\), replacing the label 2 with \(n+1\) results in an AR-labeling irrespective of where the edge label 2 is placed since \(n>4\). Suppose \(m = n+2\), replace the labels 2 and 3 with \(n+1\) and \(n+2\) respectively. The only vertex that raises a concern is the one on which the edge with label \(n+2\) is incident along with another edge with label \(x<n\). Labeling the possible remaining edge incident on that vertex using label 2 results in an AR-labeling of the graph. Similarly, if \(m = n+3\), replace the labels 2, 3 and 4 with \(n+1\), \(n+2\) and \(n+3\) respectively. The only vertex that raises concern is the one on which the edge having label \(n+3\) is incident along with another edge with label \(x\leq n\). Labeling the possible remaining edge on that vertex as 2 gives an AR-labeling. Hence the result follows. \(\square\)
The Sierpi\(\acute{\text{n}}\)ski graphs are typically used in complicated frameworks, fractals and recursive assemblages. Different networks associated with these graphs have applications in computer science, physics and chemistry [7]. The Sierpi\(\acute{\text{n}}\)ski graphs \(S(n,3)\) are defined in the following way [8]:
\(V(S(n,3)) = \{1,2,3\}^n\),
two different vertices \(u= (u_1,u_2,\ldots,u_n)\) and \(v = (v_1,v_2,\ldots,v_n)\) being adjacent if and only if there exists an \(h \in \{1,2,\ldots,n\}\) such that
\(u_t = v_t\), for \(t=1,2,\ldots,h-1\);
\(u_h \neq v_h\); and
\(u_t = v_h\) and \(v_t = u_h\) for \(t = h+1, h+2, \ldots, n\).
All Sierpi\(\acute{\text{n}}\)ski graphs have maximum degree 3 and their vertices can be partitioned into disjoint union of vertices of \(C_3\). Hence by Corollary 4.3, all Sierpi\(\acute{\text{n}}\)ski graphs are AR-graphs. Though the corollary proves the existence of an AR-labeling which makes \(S(n,3)\) an AR-graph, the actual labeling is not obtained. In the proof of the following theorem, we give an explicit labeling for \(S(n,3)\).
Theorem 5.1. The Sierpe\(\acute{\text{n}}\)ski graph \(S(n,3)\) is an AR-graph for every \(n \in \mathbb{N}\).
Proof. \(S(1,3)\), being a triangle is trivially an AR-graph. The edge labeling of the induced \(S(2,3)\) in the upper half of Figure 5 shows that \(S(2,3)\) is an AR-graph. From \(S(2,3)\), we are giving an iterative method as an explicit labeling technique for Sierpi\(\acute{\text{n}}\)ski graph with \(n>2\). The labeling of \(S(3,3)\) is given as an example in Figure 5.
For \(n>3\), the iterative labeling technique for \(S(n,3)\) starts using the labels of \(S(3,3)\) in Figure 5. Since \(S(n,3)\) is made up of three copies of \(S(n-1,3)\) along with three edges which connect them, we call the three copies, M-Block, L-Block and R-Block. We label the edges in the M-Block using the exact labels from \(S(n-1,3)\). The edge in L-Block corresponding to the edge labeled \(k\) in \(S(n-1,3)\) is labeled \(\alpha +k\), where \(\alpha\) denotes the number of edges in \(S(n-1,3)\). Similarly, the edge in R-Block corresponding to the edge labeled \(k\) in \(S(n-1,3)\) is labeled \(2\alpha +k\). There are three more edges left to be labeled. Let them be \(e_{ml}, e_{mr}\) and \(e_{lr}\) where the suffices denote the blocks on which the edge is incident on. Let \(e_{ml}\) be incident on the vertices \(v_l^m\) and \(v_m^l\), where \(v_l^m\) denotes the vertex in L-Block adjacent to \(e_{ml}\) and \(v_m^l\) represents the vertex in M-Block adjacent to \(e_{ml}\). Similarly, let \(e_{lr}\) be incident on \(v_l^r\) and \(v_r^l\), and \(e_{mr}\) be incident on \(v_r^m\) and \(v_m^r\). Label the edge \(e_{ml}\) with \(3\alpha + 1\). Now, if \(n\) is even, \(e_{lr}\) is labeled \(3\alpha + 3\) and \(e_{mr}\) is labeled \(3\alpha + 2\). If \(n\) is odd, \(e_{lr}\) is labeled \(3\alpha + 2\) and \(e_{mr}\) is labeled \(3\alpha + 3\).
We claim that the above labeling is an AR-labeling. The restriction of Lemma 2.7 to three elements shows that all vertices other than the vertices adjacent to edges \(e_{lr}\), \(e_{mr}\) and \(e_{ml}\) are AR-vertices. Now consider \(v_m^l\) and \(v_m^r\), the set of edge labels incident on them is of the form \(\{k, k+1, 3\alpha + c\}\) where \(c\) is a non-negative integer and \(k \in \mathbb{N}, k < \alpha\). By Lemma 2.3, \(v_m^l\) and \(v_m^r\) are AR-vertices. For \(v_l^m\), the set of edge labels incident is of the form \(\{\alpha + 1, \alpha + 2, 3\alpha + 1\}\) and for \(v_r^m\), the set of edge labels incident is of the form \(\{2\alpha + 1, 2\alpha + 2, 3\alpha + c\}\) where \(c \in \{2,3\}\). By Lemma 2.3, \(v_l^m\) and \(v_r^m\) are also AR-vertices. Before considering \(v_l^r\) and \(v_r^l\), the remaining two vertices, we observe that the number of edges in \(S(n,3)\) is odd if and only if \(n\) is odd. \(S(1,3)\) has 3 edges, \(S(2,3)\) has \(3(3)+3 = 12\) edges, \(S(3,3)\) has \(3(12)+3 = 39\) edges. \(|E(S(n,3))| = 3|E(S(n-1,3))| + 3\), means the number of edges in \(S(n,3)\) alternatively becomes even and odd. Using this observation, we can see that the edge \(e_{lr}\) is always labeled an even number in our specific labeling mentioned above. Since the labels of edges incident on \(v_l^r\) as well as \(v_r^l\) are consecutive natural numbers, their sum is always odd and by Lemma 2.3, both vertices are AR-vertices. Hence, the result follows. \(\square\)
The Sierpi\(\acute{\text{n}}\)ski gasket graphs \(S_n, n \geq 1\), can be defined geometrically as the graph whose vertices are the intersection points of the line segments of the finite Sierpi\(\acute{\text{n}}\)ski gasket \(\sigma_n\) and line segments of the gasket as edges [8]. \(S_1\), being a triangle, is trivially an AR-graph. Figure 6 shows that \(S_2\) and \(S_3\) are also AR-graphs.
Theorem 5.2. The Sierpi\(\acute{\text{n}}\)ski Gasket Graph \(S_n\) is an AR-graph for every \(n \in \mathbb{N}\).
Proof. We label each graph inductively using the labels from the preceding graph. Let us identify the Sierpi\(\acute{\text{n}}\)ski Gasket Graph \(S_n\) with \(n > 2\) as having three blocks of \(S_{n-1}\) in which each pair of blocks share one common vertex. We call those blocks, the M-block, L-Block and R-Block (Middle, Left and Right). The vertex common to the blocks are named \(v_{lm}\), \(v_{mr}\) and \(v_{lr}\), the suffices denoting the blocks that share the vertex.
We label the \(3^n\) edges of \(S_n\) thus. The M-Block is labeled identically to our labeling of \(S_{n-1}\). Every edge gets the same label from \(S_{n-1}\). The edges of L-Block are labeled as \(3^{n-1} + w(e)\) where \(w(e)\) denotes the label of the corresponding edge in \(S_{n-1}\). The edges of R-Block are labeled as \(2 \times 3^{n-1} + w(e)\) where \(w(e)\) denotes the label of the corresponding edge in \(S_{n-1}\).
Let us consider labeling \(S_n\) using the labels we gave for \(S_3\). Using the restriction of Lemma 2.7 to three elements, we have all the vertices of \(S_n\) other than \(v_{lm}\), \(v_{mr}\) and \(v_{lr}\) as AR-vertices. Now consider \(v_{lm}\), the edges incident are labeled \(3^{n-2} + 1, 3^{n-2} + 2, 3^{n-1} + 5\) and \(3^{n-1} + 9\). Since \(n \geq 4\) and \(1+9 \neq 2+5\), \(v_{lm}\) is an AR-vertex. The edges incident on \(v_{mr}\) are labeled \(3^{n-2} + 6, 3^{n-2} + 8, 2 \times 3^{n-1} + 5\) and \(2 \times 3^{n-1} + 9\). Since \(n \geq 4\) and \(6+9 \neq 8+5\), \(v_{mr}\) is an AR-vertex. For \(v_{lm}\), the edges incident are labeled \(3^{n-1} + 6, 3^{n-1} + 8, 2 \times 3^{n-1} + 1\) and \(2 \times 3^{n-1} + 2\). Since \(6+8 > 2\) and \(6 + 2 \neq 8 + 1\), \(v_{lm}\) is also an AR-vertex. Hence the result follows. \(\square\)
A binary tree is a tree structure in which each node has at most two children, referred to as the left child and the right child. A perfect binary tree \(T_{r,2}\) is a binary tree in which all interior nodes have two children and all leaves have the same depth \(r\) (the depth of a node \(v\) is defined as the number of edges from the root node to \(v\)) [17]. Similarly, A perfect \(t-\)ary tree \(T_{r,t}\) is a \(t-ary\) tree in which all interior nodes have \(t\) children and all leaves have the same depth \(r\) [17]. The perfect \(3-\)ary tree \(T_{r,3}\) is also called perfect ternary tree.
For \(t\geq2\) and \(r\geq1\), a glued \(t-\)ary tree \(GT(r,t)\) is obtained from two copies of a perfect \(t-\)ary tree by pairwise identification of their leaves. The vertices obtained by identification are called quasi-leaves of \(GT(r,t)\). Glued binary trees \(GT(r,2)\) are used in quantum computing and can be used to solve problems exponentially faster than classical algorithms [2, 14]. The concept of glued \(t-\)ary trees can be generalized by gluing \(n\) perfect \(t-\)ary trees, instead of two [9]. More precisely, the \(n^{th}\) generalized glued \(t-\)ary tree \(GT_{r,t}^{(n)}\) of depth \(r\) is obtained from \(n\) copies of \(T_{r,t}\) by identifying their leaves.
Theorem 6.1. The perfect binary trees \(T_{r,2}\) are AR-graphs for every \(r \in \mathbb{N}\).
Proof. Consider an arbitrary perfect binary tree with depth \(r\). Label the pendant edges from one end, say from the leftmost leaf, continuously using numbers 1 to \(2^r\). After that, label the remaining edges incident on the supporting vertices(edges in the immediate next level) continuously from \(2^r + 1\) to \(2^r + 2^{r-1}\) starting from the rightmost edge incident on the supporting vertex. Once all the edges in this level are labeled, continue labeling the next level of edges, starting from the leftmost edge. The process is continued till all the edges are labeled, with the first edge to be labeled after each level is alternating between the leftmost and rightmost ones. It is like labeling the edges from 1 to \(m\) in a continuous fashion where each new higher level of edges is labeled starting from the edge which is adjacent to the immediate previous pair of edges labeled. This is an AR-labeling of a perfect binary tree when the depth \(r \neq 4a+1, a\in \mathbb{N}\). An illustration of the labeling technique is given for \(T_{3,2}\) in Figure 7.
The origin vertex with degree 2, as well as the leaves, are trivially AR-vertices by Lemma 2.1. All other vertices have the set of edge labels incident on them to be \(\{k, k+1, \alpha\}\) for some odd \(k \in \mathbb{N}\) and \(\alpha \in \mathbb{N}\). For an arbitrary non-support vertex \(u\) of degree three, we can write \(k = \beta + k’\) where \(\beta = 2^r + 2^{r-1} \ldots + 2^j\) for some \(j \in \mathbb{N}, j < r-1\) and \(k’ < 2^{j-1}\), Now \(\alpha\) being an edge label in the immediate higher level of edges labeled \(k\) and \(k+1\), it will be bounded by the highest edge label assigned in that level, that is \(\alpha \leq \beta + 2^{j-1} + 2^{j-2}\). But then \(2k + 1 > \alpha\). Hence by Lemma 2.3, \(u\) is an AR-vertex.
The only vertices left are the support vertices of the graph. Let \(v\) be an arbitrary support vertex of the binary tree, the set of edge labels incident on \(v\) are \(\{k, k+1, \alpha\}\) for some odd \(k \in \mathbb{N}\) and \(\alpha \in \mathbb{N}\) where \(\alpha = 2^r + 2^{r-1} – \frac{k+1}{2}\) + 1. By Lemma 2.3, \(v\) is an AR-vertex if \(2k + 1 \neq \alpha\). Assuming equality and simplifying would lead to the equation \(2^r + 2^{r+1} = 5k + 1\). This is true only when \(r = 4a+1, a \in \mathbb{N}\). So when \(r\) is not of the form \(4a+1, a \in \mathbb{N}\), the above labeling would be an AR-labeling of the perfect binary tree with depth \(r\).
Now let us consider the number of levels \(r\) to be of the form \(4a+1, a \in \mathbb{N}\). For example, if \(r = 5\), we have \(k= 19\) such that the above labeling would result in a supporting vertex with incident edge labels {19, 20, 39} which is not an AR-vertex by Lemma 2.3. Similarly, when \(r = 9\), the labeling would give rise to a supporting vertex having incident edge labels {307, 308, 615}, which by the same Lemma is not an AR-vertex. So, for binary trees with number of levels \(r\) = \(4a+1, a \in \mathbb{N}\), we swap the edge labels of supporting vertices \(\{v_1, v_2\}\), the former adjacent to edge labels \(k\) and \(k+1\), the latter adjacent to edge labels \(k-1\) and \(k-2\) where \(k\) is such that \(5k = 2^r + 2^{r+1} – 1\). Since the third edge label incident on \(v_2\) is \(2k + 2\) in this case, swapping the edge labels of non-pendant edges would result in \(v_1\) and \(v_2\) being \(AR\) by Lemma 2.3 since the sets of edge labels incident on them will be respectively \(\{k, k+1, 2k+2\}\) and \(\{k-1, k-2, 2k+1\}\). Hence perfect binary trees with depth \(r = 4a+1, a \in \mathbb{N}\) are also AR-graphs. \(\square\)
Theorem 6.2. The generalized glued binary trees \(GT_{r,2}^{(n)}\) are AR-graphs, for \(n\leq4\).
Proof. The glued binary tree \(GT(1,2)\) corresponds to cycle \(C_4\) which is trivially \(AR\). \(GT_{1,2}^{(3)}\) and \(GT_{1,2}^{(4)}\) denote respectively complete bipartite graphs \(K_{2,3}\) and \(K_{2,4}\) which are shown to be AR-graphs in Figure 8. So we only need to consider generalized glued binary trees with depth at least two from now on. Let us consider an arbitrary glued binary tree \(GT(r,2)\) with \(r>1\). We label the first copy of the binary tree from 1 to \(\mu\) as in \(Theorem~ 5\), where \(\mu\) denotes the total number of edges in one copy of the binary tree. Label the edges of the second copy of the binary tree using edge labels \(\mu + 1\) to \(2\mu\) in the following way. Corresponding to the edge labeled \(k\) in the first copy, label the edge in the second copy as \(\mu + k\). This will be an AR-labeling of \(GT(r,2)\) with \(r>1\).
The quasi leaves and two origin vertices having degree 2 are trivially AR-vertices by Lemma 2.1. The vertices in the first copy of the binary tree are all AR-vertices and since the set of edge labels incident on an arbitrary vertex \(v\) of degree three in the second copy of the binary tree is \(\{\mu + a_1, \mu + a_2, \mu + a_3\}\) in which \(\{a_1, a_2, a_3\}\) is the set of edge labels incident on an AR-vertex in the first copy, the restriction of Lemma 2.7 to three vertices would then make \(v\) an AR-vertex. Hence all glued binary trees \(GT(r,2)\) are AR-graphs. Figure 9 demonstrates the labeling with the example of \(GT(3,2)\).
Moving onto generalized glued binary trees with three copies \(GT_{r,2}^{(3)}\), the labeling of the first two copies follows from \(GT(r,2)\) and in the third copy, corresponding to edges labeled \(k\), the edges in the third copy are labeled \(2\mu + k\). Vertices except the quasi leaves in the third copy of the binary tree are AR-vertices from the same argument we used while attaching the second copy. Hence, by Lemma 2.1 and a restriction of Lemma 2.7 to three vertices, all the vertices apart from the quasi leaves are AR-vertices. For all quasi leaves, the edge labels incident on them are \(\{k, \mu + k, 2\mu + k\}\). These quasi leaves are hence AR-vertices by \(Lemma~ 3\) since \(k < \mu\). The labeling is an AR-labeling of \(GT_{r,2}^{(3)}\).
While considering the generalized glued binary tree with four copies \(GT_{r,2}^{(4)}\), we label the first three copies of the binary tree except for the edges incident on the quasi leaves using the labels used for \(GT_{r,2}^{(3)}\). Corresponding to edges labeled \(k\), the edges other than those incident on the quasi leaves in the fourth copy, are labeled \(3\mu + k\). All but the quasi leaves and support vertices of the fourth copy of the binary tree will be AR-vertices by Lemma 2.1 and the restriction of Lemma 2.7 to three vertices. We rotate cyclically the edge labels in the fourth copy of the binary tree corresponding to edges labeled 1, 4, 3 and 2 in the first copy of the binary tree. Now for all remaining edge labels from the supporting vertices of the fourth copy of the binary tree, we swap the corresponding labels of the pendant edges from the same supporting vertex in the fourth copy. That is, corresponding to the edge labeled \(k\), \(k\) being odd \(k\neq 1, 3\), the edge in the fourth copy will be labeled \(3\mu + k + 1\). The edges corresponding to the edges labeled \(l\) in the first copy, \(l\) being even, \(l\neq 2, 4\), are labeled \(3\mu + l – 1\) in the fourth copy.
Now the set of edge labels of quasi leaves can be classified into two sets and four remaining vertices. Vertices with set \(A\) of edge labels \(\{k, \mu + k, 2\mu + k, 3\mu + k + 1\}\), set \(B\) of edge labels \(\{l, \mu + l, 2\mu + l, 3\mu + l – 1\}\) with \(k\) being odd and \(l\) even. The four quasi leaves will have edge labels \(\{1, \mu + 1, 2\mu + 1, 3\mu + 4\}\), \(\{4, \mu + 4, 2\mu + 4, 3\mu + 3\}\), \(\{3, \mu + 3, 2\mu + 3, 3\mu + 2\}\) and \(\{2, \mu + 2, 2\mu + 2, 3\mu + 1\}\). Also, the two supporting vertices in the first copy of the binary tree will have sets of labels of incident edges to be \(\{1,4,\gamma\}\) and \(\{2,3,\gamma + 1\}\). Since \(k \neq 1\), vertices in \(A\) will be AR-vertices by Observation 2.10, Vertices in \(B\) will be AR-vertices by Lemma 2.8. The four quasi leaves are AR-vertices by Observation 2.10 and Lemmas 2.4 and 2.8. The two supporting vertices will be AR-vertices if \(r>2\) by Lemma 2.3, since \(r>2\) implies \(\gamma > 8\). Hence, the labeling is an AR-labeling of \(GT_{r,2}^{(4)}\) with \(r>2\). When \(r=2\), interchange the labels \(5\), which is \(\gamma\) and \(11\) which is \(\mu + \gamma\). Since \(11\) is incident on a degree two vertex and a degree three vertex having consecutive numbers, say \(x\) and \(x+1\) as labels of two incident edges with \(x>6\), by Lemma 2.1 and Lemma 2.3, swapping edge labels between \(5\) and \(11\) would result in an AR-labeling of \(GT_{2,2}^{(4)}\). Hence the result. \(\square\)
Theorem 6.3. The perfect ternary trees \(T_{r,3}\) are AR-graphs for every \(r \in \mathbb{N}\).
Proof. Figure 10 shows that perfect ternary tree with \(r=3\) is an AR-graph. One can easily deduce from Figure 10 that \(T_{r,2}\) is also an AR-graph. This labeling can be extended to arbitrary \(r\) levels by continuing the labeling with consecutive natural numbers. After each level, labeling of the next lower level commences from the leftmost edge of the level. There are four vertices say \(v_1, v_2, v_3, v_4\) in the first three levels with sets of edge labels incident on them being respectively \(\{1, 3, 5\}\), \(\{1, 2, 4, 12\}\), \(\{2, 13, 14, 17\}\) and \(\{4, 15, 16, 18\}\). Now \(v_1\) is an AR-vertex by Lemma 2.2, \(v_2\) is an AR-vertex by Lemma 2.13 and \(v_3\) and \(v_4\) can be verified to be AR-vertices. All the remaining vertices in the ternary tree have sets of edge labels of the form \(\{a, k, k+1, k+2\}\) for some \(k \in \mathbb{N}, k>a\). Since \(2 < a < k-1\), by Observation 2.12, all those vertices are AR-vertices. Hence the result. \(\square\)
Theorem 6.4. The generalized glued ternary trees \(GT_{r,3}^{(n)}\) are AR-graphs, for \(n\leq4\).
Proof. Glued ternary trees with depth one, \(GT_{1,3}^{(n)}\) needs to be labeled distinctly from the rest. Figure 11 is an AR-labeling of \(GT_{1,3}^{(4)}\). Removing the origin vertex on which the the edges with maximum labels are incident will result in the AR-labeling of the \(GT_{1,3}^{(3)}\) and subsequent removal of another origin vertex with the same criterion will result in the AR-labeling of \(GT_{1,3}^{(2)}\).
While labeling all other glued ternary trees with two copies \(GT(r,3)\), we can label the first copy of the ternary tree with the labeling technique used for labeling perfect ternary trees. The second copy is labeled in the following manner; Corresponding to every edge labeled \(k\) in the first copy, the edge in the second copy is labeled \(\alpha + k\) in the second copy where \(\alpha\) denotes the number of edges in the first copy of the ternary tree. The quasi leaves will be AR-vertices due to Lemma 2.1. A restriction of Lemma 2.7 to three vertices shows that the origin vertex of the second copy is an AR-vertex. A direct application of Lemma 2.7 ensures that all other vertices in the second copy of the perfect ternary tree are AR-vertices. Figure 12 demonstrates this labeling technique on \(GT(2,3)\).
Moving onto generalized glued ternary trees with three copies \(GT_{r,3}^{(3)}\), we can label the first two copies using the same labels from \(GT(r,3)\). In the third copy of the ternary tree all the edges corresponding to edges labeled \(k, k< \alpha – 1\) in the first copy are labeled \(2\alpha + k\). The labeling of the final two edges is interchanged so that the vertices, say \(v_1\) and \(v_2\) on which they are incident on ends up being adjacent to sets of edge labels \(\{\alpha, 2\alpha, 3\alpha – 1\}\) and \(\{\alpha – 1, 2\alpha – 1, 3\alpha\}\). \(v_1\) and \(v_2\) are AR-vertices by Lemma 2.3. All the remaining vertices are AR-vertices by Lemma 2.7 and its restriction to three vertices.
While considering generalized glued ternary trees with four copies \(GT_{r,3}^{(4)}\), the labels to edges incident on quasi leaves have to be given differently from the rest. Consider \(GT_{r,3}^{(4)}\) with \(r\geq4\). Let \(v\) be an arbitrary supporting vertex in the first copy of the ternary tree. Let \(v_1\), \(v_2\) and \(v_3\) be the quasi leaves adjacent to \(v\), who share the edges labeled \(\beta, \beta – 1\) and \(\beta – 2\) with \(v\). The edges shared by these three leaves with \(v’, v”\) and \(v”’\), the supporting vertices corresponding to \(v\) in the second, third and fourth copies will be labeled in such a way that the set of edge labels incident on \(v_1\) is \(\{\beta, 2\beta, 3\beta – 1, 4\beta\}\), \(v_2\) is \(\{\beta – 1, 2\beta – 2, 3\beta – 2, 4\beta – 2\}\), \(v_3\) is \(\{\beta – 2, 2\beta – 1, 3\beta, 4\beta – 1\}\). Direct verification shows that all the quasi leaves are AR-vertices under this labeling. Since the labeling hasn’t changed the set of edge labels in vertices other than quasi leaves, all the remaining edges in the first three copies are labeled as in the case of \(GT_{r,3}^{(3)}\) and the edges in the fourth copy in such a way that the edge corresponding to the edge labeled \(k\) in the first copy is labeled \(3\alpha + k\). Lemma 2.7 and its restriction to three vertices ensures that remaining vertices in the fourth copy of the ternary tree are also AR-vertices. Hence the result is true for all \(GT_{r,3}^{(4)}\) with \(r\geq4\).
In \(GT_{2,3}^{(4)}\), there exists a supporting vertex which has a non-consecutive set of edge labels incident. We proceed to label the edges in the three remaining copies in such a way that the set of edge labels incident on those three vertices will be \(\{2,16,36,48\}\), \(\{4,24,26,40\}\) and \(\{12,14,28,38\}\). Since all other supporting vertices have consecutive numbers as labels of edges incident on them, we proceed to label the corresponding edges in the remaining copies the same way as we did when \(r\geq 4\). This is an AR-labeling of \(GT_{2,3}^{(4)}\).
In \(GT_{3,3}^{(4)}\), there exist two supporting vertices which have non-consecutive sets of edge labels incident. we proceed to label the edges in the three remaining copies in such a way that the set of edge labels incident on those six vertices will be \(\{13,52,91,131\}\), \(\{14,53,92,134\}\), \(\{17,56,95,130\}\), \(\{15,54,93,133\}\), \(\{16,55,94,135\}\) and \(\{18,57,96,132\}\). Since all other supporting vertices have consecutive numbers as labels of edges incident on them, we use the same labeling technique mentioned above for other edges in the remaining copies of the perfect ternary tree. This is an AR-labeling of \(GT_{3,3}^{(4)}\). So, the result is true for \(GT_{r,3}^{(4)}\) for every \(r \in \mathbb{N}\). Hence the theorem follows. \(\square\)
Though this paper contains results about some cubic AR-graphs, whether all cubic graphs are AR-graphs is still an open question. In fact, identifying AR-graph classes seems to be an interesting venture. Can some parameterical bounds be obtained for AR-graphs will also be an interesting question. As a whole, this paper merely introduces the notion of AR-labeling. AR-labeling in general, and AR-graphs in particular, offers plenty of directions for research.
Obviously, just like stars \(K_{1,n}\) with \(n>2\), there are infinitely many non AR-graphs, but the following theorem shows the existence of AR-labeling for every graph.
Theorem 7.1. Given a graph G, there exists an \(AR-\)labeling of \(G\).
Proof. Let \(G\) be a graph with \(m\) edges. Label the edges from 1 to \(m\). Define the function \(f:E \rightarrow \mathbb{N}\), \(f(i)=2^{i-1}\). Then, \(f\) is an \(AR\) labeling of \(G\). (Since sums of distinct powers of 2 are always distinct). \(\square\)
Since every graph has an AR-labeling using sufficiently large natural numbers, the immediate optimization question would be to ask for the smallest natural number \(k\) such that there exists an AR-labeling from the edge set of the graph to natural numbers from 1 to \(k\). Hence, we define the notion of AR-index, which gives a rough idea of how close a graph is to being an AR-graph.
Definition 7.2. The minimum \(k\) such that there exists an AR-labeling \(f:E\rightarrow \{1,2,3,\dots,k\}\) is called the AR-index of G, denoted by \(ARI(G)\).
Combining the restriction imposed by \(m(G)\) and the edge labeling mentioned in Theorem 7.1, we have \(m(G)\leq ARI (G) \leq 2^{m-1}.\) AR-graphs can be identified as graphs \(G\) with \(ARI(G) = m(G)\). Evaluating the AR-index of graph classes will be another possible area of research which can be extensively explored in the future.
The first author is supported by the Senior Research Fellowship (09/0239(17181)/2023-EMR-I) of CSIR (Council of Scientific and Industrial Research, India).
The authors declare no conflicts of interest.
This study is theoretical and does not involve the generation or analysis of datasets.
All the authors contributed equally. All authors have read and agreed to the published version of the manuscript.