ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.1111733 J. Algebra Comb. Discrete Appl. 9(2) • 101–114 Received: 3 February 2021 Accepted: 22 October 2021 Journal of Algebra Combinatorics Discrete Structures and Applications On the generation of alpha graphs Research Article Christian Barrientos Abstract: Graceful labelings constitute one of the classical subjects in the area of graph labelings; among them, the most restrictive type are those called α-labelings. In this work, we explore new techniques to generate α-labeled graphs, such as vertex and edge duplications, replications of the entire graph, and k-vertex amalgamations. We prove that for some families of graphs, it is possible to duplicate several vertices or edges. Using k-vertex amalgamations we obtain an α-labeling of a graph that can be decomposed into multiple copies of a given α-labeled graph as well as a robust family of irregular grids that can α-labeled. 2010 MSC: 05C78, 05C51 Keywords: α-labeling, Graceful graph, Amalgamation, Duplication, Replication 1. Introduction The roots of difference vertex labelings can be found in the area of combinatorial design, in particular, this type of graph labeling was introduced as a mechanism to determine the veracity of two conjectures associated with the decomposition of complete graphs into copies of a given tree. The first of these conjectures, due to Ringel [13], states that the complete graph K2n+1 can be decomposed into copies of any tree of size n. The second conjecture, posed by Kotzig [10], goes even further by adding the condition that the decomposition is cyclic. Let G be a graph of size n, a difference vertex labeling of G is a one-to-one function f : V (G) → S, where S is a set of non-negative integers, with the property that every uv ∈ E(G) has associated a weight determined by |f(u) − f(v)|. In [14], Rosa defined four of these labelings by introducing some conditions to the set S and to the set of weights induced by the function. Rosa said that the function f is a β-valuation if S = {0, 1, . . . ,n} and the set of weights is W = {1, 2, . . . ,n}. Years later, Golomb [7] used the term graceful labeling to refer to this valuation. Graceful labelings are a special case of another labeling introduced by Rosa. A ρ-valuation satisfies S = {0, 1, . . . , 2n} and the set of weights is W = {w1,w2, . . . ,wn}, where wi = i or wi = 2n + 1−i. Rosa [14] proved that a cyclic decomposition of K2n+1 into copies of a given graph of size n exists if and only if Christian Barrientos; Department of Mathematics, Valencia College, Orlando, FL 32832, USA (email: chr_barrientos@yahoo.com). 101 https://orcid.org/0000-0003-2838-8687 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 there exists a ρ-labeling of G. Therefore, in these three articles we can see the origin of the most famous conjecture in the area of graph labeling, known as the graceful tree conjecture that expresses that every tree admits a graceful labeling. Rosa and Širáň [16], introduced the concept of bipartite labeling of a tree. In [3], Barrientos and Minion extended their definition to include all bipartite graphs. Let G be a bipartite graph and {A,B} be the natural bipartition of V (G); we refer to A and B as the stable sets of G and reserve the symbols a and b to represent the respective cardinalities of these sets. Assuming that G is a bipartite graph, a difference vertex labeling of G is said to be bipartite if there exists an integer λ, called the boundary value of f, such that f(u) ≤ λ < f(v) for every (u,v) ∈ A × B. In [14], Rosa defined an α-valuation (or α-labeling) as a bipartite graceful labeling. We say that an α-graph is any graph that admits an α-labeling. Rosa [14] proved that if a graph G of size n admits an α-labeling, then there exists a cyclic decomposition of K2tn+1 into subgraphs isomorphic to G, where t is any natural number. This labeling is the most versatile of the labelings introduced by Rosa; it can be transformed into several types of labelings such as harmonious, magic, and antimagic. A detailed description of its interaction with other labelings can be found in [11] and also in [19]. Thus, the study of α-graphs has implications in other related research areas. This work is completely devoted to the study of this labeling. In Section 2 we introduce some existing results that are used in the coming sections to build new families of α-graphs. In Section 3 we work with the concept of vertex duplication, proving that any vertex of a caterpillar can be duplicated to produce a new α-graph; we go even further, proving that an α-graph is obtained when any number of pairwise non-adjacent vertices of a caterpillar are duplicated. In Section 4 we study edge-duplications, proving that a graceful graph is obtained when an edge of a cycle is duplicated and when the size of the cycle is even the labeling obtained is in fact an α-labeling. Moreover, we prove a similar result if two selected edges of a cycle are duplicated. We conclude that section by proving that any number of edges on the spine of a caterpillar can be duplicated and the outcome is an α-graph. In Section 5 we extend the idea of vertex duplication; now we duplicate every vertex of a graph with an action that resembles the Cartesian and the (weak) tensor product of a graph and a path. We show that when a graph admits an α-labeling and all the vertices are duplicated the same number of times, the final graph is also an α-graph. In Section 6 we analyze the process of vertex amalgamation by studying some conditions that allow us to amalgamate multiple vertices of α-labeled graphs. This construction is used to generate new α-graphs, among the graphs obtained we have a supersubdivision of cycles of even size and a family of quadrangular cacti whose bases are some α-trees. We finish this section introducing a family of graphs whose vertices are points in the orthogonal integer lattice; we call these graphs irregular grids; an α-labeling for these grids is obtained using the tools presented in this section. The reader interested in this type of problems can find more information in the work of López and Muntaner-Batle [11] and in Gallian’s survey [6]. All graphs considered here are finite with no loops nor multiple edges. The technical terminology not defined here is taken from [5] and/or [6]. 2. The essential results Since the introduction of the concepts of graceful and α-labeling, many results have been obtained. In this section we provide, without proof, some of the results that are essential in the coming sections. Suppose that G is a graph of size n and f is a difference vertex labeling of G. A shifting of f in c units is the labeling g of G defined for every v ∈ V (G) as g(v) = f(v) + c; clearly, the weight of any given edge of G is the same under both labelings. If f is a graceful labeling, its complementary labeling is the function f defined as f(v) = n − f(v) for every v ∈ V (G). If f is an α-labeling with boundary value λ, then f is an α-labeling with boundary value n − λ. Note that if f assigns the label 0 on the stable set A, f does it on the stable set B; in other terms, if f assigns the smaller labels to the elements of A, f assigns the larger labels on this stable set. Each α-labeling of G is also associated with other two important labelings of G; the first one is called the reverse of f, denoted by fr, and is defined as fr(v) = λ−f(v) if f(v) ≤ λ and fr(v) = n + λ + 1 −f(v) if f(v) > λ. Take note of the fact that fr is 102 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 also an α-labeling; thus, in general terms, the number of graceful labelings of a graph is always divisible by 2 and the number of α-labelings is always divisible by 4. This labeling was also introduced by Rosa [15] but under the name of inverse labeling. A graph G of size n is said to be arbitrarily graceful if for every positive integer d, there exists a difference vertex labeling that induces the weights d,d + 1, . . . ,d + n − 1. When d > 1, the function is called d-graceful labeling. For any positive integer d, an α-labeling f of G can be transformed into a d-graceful labeling, this transformation (also called amplification) can be done by adding the constant d − 1 to each vertex label larger than the boundary value of f. This property of the α-labelings was proven, independently, by Maheo and Thuillier [12] and Slater [18]. In the coming sections, we transform some of the α-labelings into d-graceful labelings, to obtain, new and larger α-graphs. When G is an α-tree of size n and f is an α-labeling of G with boundary value λ, the associated d-graceful labeling shifted c units assigns the labels in the set {c,c + 1, . . . ,λ + c}∪{λ + c + d,λ + c + d + 1, . . . ,n + c + d−1} and induces the weights in the set {d,d + 1, . . . ,n + d− 1}. In [14], Rosa proved, among other results, the existence of α-labelings for two types of graphs used in this work, caterpillars and cycles of size divisible by 4. In Figure 1 we show an example of these labelings using a caterpillar and a cycle, both of order 12. The distribution of the labels can be extended to any other member of the respective family. 11 10 9 8 7 6 0 1 2 3 4 5 12 11 10 9 8 7 0 1 2 4 5 6 Figure 1. A caterpillar and a cycle with their respective α-labeling Let G1 and G2 be two graphs; a graph G is the result of a vertex amalgamation of G1 and G2 if a vertex of G1 is identified (merged) with a vertex of G2. Let G1 and G2 be α-labeled graphs, it is well-known that the chain graph obtained amalgamating G1 and G2 is an α-graph; the amalgamation is done by identifying the vertex labeled 0 of G2 with the vertex of G1 which label is the boundary value of its α-labeling. Furthermore, a wider category of graphs is obtained if G2 is just a graceful graph; in this case, we obtain a graceful chain graph. The k-vertex amalgamation of G1 and G2 is the graph obtained by identifying k independent vertices of G1 with k independent vertices of G2. In Section 6 we discuss an alternative to use this multi-vertex amalgamation to generate new α-graphs. An edge amalgamation of G1 and G2 is the process of identifying an edge of G1 with an edge of G2. If both graphs have been α-labeled, there is an α-graph G that is the result of the amalgamation of the edge of weight n1 in G1 with the edge of weight 1 in G2, where n1 is the size of G1. This result was proven by Barrientos and Minion in [2]. Observe that in both types of amalgamations, the second condition that asks for two α-graphs can be replaced by an α-graph and a graceful graph, but now the outcome is a graceful graph instead of an α-graph. The following definition was given by Sethuraman and Selvaraju [17]. Let G be a graph of order m and size n; a graph H is called a supersubdivision of G if H is obtained from G by replacing every edge e of G by a complete bipartite graph K2,se in such a way that the end-vertices of e are amalgamated with the vertices of the 2-element stable set of K2,se and the edge e is deleted. Note that the complete bipartite graphs used in these replacements do not need to be isomorphic. In [1], Barrientos and Barrientos proved that any graph of positive size has a supersubdivision that admits an α-labeling. 103 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 3. Duplicating vertices The duplication of a vertex v of a graph G is the graph G′ obtained from G by adding a new vertex v′ to G and connecting v′ to all the neighbors of v. In [9], Kaneria et al. proved that the duplication of a vertex of a cycle of even size is graceful. In the following proposition we prove that every vertex of a caterpillar can be duplicated to produce a new α-graph. Recall that the spine of a caterpillar is the path containing all the vertices of degree larger than 1. Proposition 3.1. Every vertex of a caterpillar can be duplicated to produce a new α-graph. Proof. Suppose that G is a caterpillar of size n. Let v ∈ V (G) be the vertex to be duplicated. If deg(v) = 1, then G′ is a caterpillar of size n + 1, which is an α-graph. Suppose that deg(v) > 1. The size of G′ is n + deg(v) and its order is n + 2. Since G is bipartite and v′ is only connected to the vertices adjacent to v, we get that G′ is also a bipartite graph. Suppose that f is the α-labeling of G that follows the pattern in Figure 1; we define an α-labeling g of G′ as follows: g(u) =   f(u) if f(u) ≤ f(v), f(u) + deg(v) if f(u) > f(v), f(v) + deg(v) if u = v′. Let u1v,u2v, . . . ,ukv be the edges of G incident to v. The weights of these edges form a set of k consecutive integers. Let wi = |f(ui) −f(v)|; without loss of generality we assume that w1 < w2 < · · · < wk. When v ∈ A, wi = f(ui) −f(v), we get g(ui) −g(v) = f(ui) + k −f(v) = f(ui) −f(v) + k = wi + k and g(ui) −g(v′) = f(ui) + k −f(v) −k = f(ui) −f(v) = wi. Thus, the weights of the edges incident to v or v′ form the set {w1,w2, . . . ,wk,w1 +k,w2 +k,. . . ,wk +k} = {w1,w1 + 1, . . . ,w1 + 2k − 1} because wi+1 = wi + 1. Let xy ∈ E(G) with x ∈ A. If f(y) −f(x) < w1, then g(y) − g(x) = f(y) − f(x) because both original labels are incremented k units. If f(y) − f(x) > wk = w1 + k − 1, then g(y) −g(x) = f(y) −f(x) + k because only the label of y increases k units. This implies that the new weight of xy is at least equal to w1 + 2k. Consequently, the set of induced weights is {1, 2, . . . ,n + k}. When v ∈ B, wi = f(v)−f(ui) and g(v)−g(ui) = wi but g(v′)−g(ui) = f(v) + k−f(ui) = wi + k. Thus, the set of weights induced on the edges incident to v or v′ is {w1,w1 + 1, . . . ,w1 + 2k − 1}. Let xy ∈ E(G) with x ∈ A. If f(y)−f(x) < w1, then g(y)−g(x) = f(y)−f(x) because none of the original labels are incremented. If f(y)−f(x) > wk, then g(y)−g(x) = f(y)−f(x) + k because only the label of y increases k units. As in the previous case, these edges have weights in {w1 + 2k,w1 + 2k + 1, . . . ,n+k}. Then, the set of induced weights is {1, 2, . . . ,n + k}. Since the largest label used is n+k, and every label is used exactly once, this is a graceful labeling of G′; moreover, the labels assigned by g to the vertices of B are larger than those assigned to the elements of A, therefore, g is an α-labeling of G′. In Figure 2 we show a sequence of examples where each internal vertex of a caterpillar has been duplicated. There are two features of the vertex duplication that we want to mention: • Let v be the vertex of G, selected to be duplicated; if deg(v) = 2, then the graph G′, can be seen, as a supersubdivision of the caterpillar G. 104 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 0 1 2 3 4 5 6 7 8 910 1112 0 1 2 3 6 7 8 9 10 1112 1314 5 0 1 2 3 4 5 10 11 12 1314 1516 9 0 1 2 3 4 5 6 7 8 910 1112 16 0 1 2 3 4 5 6 7 8 910 1115 14 0 1 2 3 4 5 6 7 8 1213 1415 11 Figure 2. α-labeled graphs obtained by duplicating every internal vertex of a caterpillar • If G is a tree, the subgraph of G induced by the edges incident to v is isomorphic to the complete bipartite graph K1,deg(v). In the case of a caterpillar with the α-labeling described before, the labels of the vertices adjacent to v form a set of consecutive integers. The labels of v and v′ are deg(v) units apart. Thus, the subgraph formed by all the edges incident to v or v′ is isomorphic to K2,deg(v) and the labeling of this graph is a shifting of a d-graceful labeling. Consequently, if instead of adding one new vertex we add any number of copies of v, the previous result still holds. In the next theorem we prove that for any subset of vertices of a caterpillar, such that the vertices in this subset are pairwise non-adjacent, we can duplicate all the elements of this set and the result is an α-graph. Theorem 3.2. Let G be a caterpillar and S be a subset of V (G). If the elements of S are pairwise non-adjacent, then an α-graph is obtained by duplicating all of them. Proof. If S contains any vertex of degree one, its duplication results in another caterpillar, which admits an α-labeling. Therefore we may assume that all the vertices in S are in the spine of the caterpillar. Let S = {v1,v2, . . . ,vs} where dist(vi,vj) ≥ 2 and the path connecting vi and vi+1 does not contain any other member of S. The graph G can be decomposed into s subgraphs, being each of them a caterpillar containing exactly one element of S. Thus, each of these caterpillars has only one vertex that has been duplicated; consequently, each of them is an α-graph. The α-labeling of each of these graphs can be amplified and shifted conveniently in such a way that there is no repetition of weights when they are taken collectively, the shiftings can be made in such a way that the vertices on the spine used in the decomposition are the only one where a label is repeated. The concatenation of these graphs is made using vertex amalgamation. Thus, an α-labeling of G′ can be obtained. In Figure 3 we show this procedure, where three vertices of the spine are duplicated, one of them more than once, and an end-vertex is also duplicated. The different colors are used to emphasize the subgraphs in the decomposition mentioned in the proof of this theorem. 105 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 30 33 4 9 10 13 16 19 20 2 27 23 21 0 1 28 29 3 26 25 24 22 17 18 Figure 3. α-labeling of a graph obtained by duplicating multiple vertices of a caterpillar 4. Duplicating edges The duplication of an edge e = uv of a graph G, is the process that consists of the introduction of an edge e′, with end-vertices u′ and v′, and the additional edges uu′ and vv′, that connect e′ to the graph G. Kaneria et al. [9] proved that the duplication of an edge of an even cycle is graceful. In the following results we extend this result by showing, first, that this is also valid with an odd cycle, and second that more edges of a cycle can be duplicated with the same end result. Proposition 4.1. If G is the result of an edge duplication of the cycle Cn, then G admits a graceful labeling when n is odd and an α-labeling when n is even. Proof. Recall that Cn is graceful if and only if n ≡ 0, 3(mod 4) and it is an α-graph if and only if n ≡ 0(mod 4). The graph G can be explained as the edge amalgamation of C4 and Cn; based on the result in [2] and the fact that C4 is an α-graph, we know that G is graceful or an α-graph depending on the value of n. So, we need to analyze the cases where Cn is not graceful. In either case we consider G as the outerplanar graph, obtained from Cn+2, with a single chord connecting two vertices located at distance 3 from each other. Note that the case n ≡ 2(mod 4) was solved in [9], i.e., we just need to study the case n ≡ 1(mod 4). We denote by v1,v2, . . . ,vn+2 the consecutive vertices of Cn+2. For n ≡ 1(mod 4), we use the following labeling of the vertices of Cn+2: f(vi) =   i−1 2 if i is odd, n + 4 − i 2 if 2 ≤ i ≤ n−1 2 is even, n + 3 − i 2 if i = n+3 2 , n + 2 − i 2 if n+7 2 ≤ i ≤ n + 1 is even. Note that when i is odd, f is increasing with range {0, 1, . . . , n+1 2 }, when i is even, f is decreasing with range {n+3 2 , n+5 2 , . . . , 3n+1 4 }∪{3n+9 4 }∪{3n+17 4 , 3n+21 4 , . . . ,n + 3}. Thus, the labels assigned by f are in the set {0, 1, . . . ,n + 3}, where n + 3 is the size of G. For each n+7 2 ≤ i ≤ n+1 even, the edge vi−1vi has weight f(vi)−f(vi−1) = n+2− i2− i−2 2 = n+3−i, while vi+1vi has weight f(vi) −f(vi+1) = n + 2 − i2 − i 2 = n + 2 − i. In other terms, the weights of the edges incident to vi are two consecutive integers. Therefore, for these values of i, the weights on all these edges form the set {1, 2, . . . , n−1 2 }. The edge v1vn+2 has weight f(vn+2) − f(v1) = n+2−12 − 0 = n+1 2 . When i = n+3 2 , vivi−1 has weight f(vn+3 2 )−f(vn+1 2 ) = n+ 3− n+3 4 − n+1 2 −1 2 = n+5 2 and vivi+1 has weight f(vn+3 2 ) −f(vn+5 2 ) = n+3 2 . Similarly, for each 2 ≤ i ≤ n−1 2 even, vi−1vi has weight n + 5 − i and vi+1vi has weight n + 4− i; thus, {n+9 2 , n+11 2 , . . . ,n + 3} is the set formed by the weights of these edges. Hence, the weights on the edges of Cn+2 form the set {1, 2, . . . ,n + 3}−{n+72 }. 106 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 Since vn−1 2 and vn−1 2 +3 are three units apart, when they are connected, the cycles C4 and Cn are formed, i.e., the graph G is obtained. The weight of the new edge is f(vn−1 2 ) − f(vn−1 2 +3) = n + 4 − n−1 4 − n+5 2 −1 2 = n+7 2 , that is, the weight that has not been obtained on Cn+2. Therefore, f is a graceful labeling of G. Let e1,e2 ∈ E(G), we define the distance between e1 and e2, denoted by dist(e1,e2), as the length of the shortest path connecting an endvertex of e1 to an endvertex of e2. In the next theorem we prove that the duplication of two edges of the cycle Cn is a graceful graph when the edges duplicated are at distance 1, 2, or 3. Theorem 4.2. Let e1,e2 be non-incident edges of Cn and G be the graph obtained from Cn by duplicating e1 and e2. If dist(e1,e2) ∈ {1, 2, 3}, then G is a graceful graph when n is odd or an α-graph when n is even. Proof. The graph G has order n + 4 and size n + 6. Let e1,e2 ∈ E(Cn) such that σ = dist(e1,e2) ∈ {1, 2, 3}. The graph G can be formed by connecting four subgraphs, denoted by G1,G2,G3,G4, where each Gi is vertex amalgamated to Gi+1 and G4 is connected to G1 with an edge. On Gi, we distinguish two vertices, denoted by ui and vi; thus, vi is amalgamated to ui+1 and an edge is used to connect v4 and u1. These subgraphs are chosen in such a way that G1 ∼= C4, C2 ∼= Pr, and G3 ∼= Ps, where s = n−r−σ and r =   n 2 if n ≡ 0(mod 4), n+1 2 if n ≡ 1(mod 4), n 2 if n ≡ 2(mod 4), n+3 2 if n ≡ 3(mod 4). The graph G4 varies with σ; in general, it can be described as the vertex amalgamation of C4 and a path of order σ. All these subgraphs admit an α-labeling. The labeling of G1 is (0, 4, 1, 2); the labeling of the paths G2 and G3 is the one given in Section 2 or its complementary; the labeling of G4 is given in the following diagram, where each residue class of n is considered, the vertices u4 and v4 are highlighted. In G1, the vertices u1 and v1 are those labeled 1 and 2, respectively. In G2 and G3, the distinguished vertices are the corresponding end-vertices. The α-labeling of G1 is transformed into a (n + 3)-graceful labeling, thus u1 is labeled 1 and v1 is labeled n + 4. For i = 2, 3, the α-labeling of Gi is chosen based on the new labeling of Gi−1, then it is amplified and shifted in such a way that the label of ui matches with the label of vi−1, in this way there is no repetition of labels, except for the vertices that are going to be amalgamated. Thus, assuming that f is the α-labeling of the path given in Section 2, the α-labeling of G2 is f shifted 2 units and amplified to produce a largest weight equal to n + 2. The α-labeling of G3 is f only when n ≡ 0(mod 4), otherwise it is f, this is amplified to produce a largest weight equal to n+4 2 when n is even, n+3 2 when n ≡ 1(mod 4), or n+1 2 when n ≡ 3(mod 4). The α-labeling of G4, taken from the previous chart, is just shifted based on the final label of v3. Then, the weights on the edges of the union of these four graphs form the set {1, 2, . . . ,n − 6} − {x}, where x = n+6 2 when n is even, x = n+5 2 when n ≡ 1(mod 4), or x = n+3 2 when n ≡ 3(mod 4). Hence, the information of the following chart holds. Final label of v3 Final label of v4 Weight of u1v4 n ≡ 0(mod 4) n/2 (n + 8)/2 (n + 6)/2 n ≡ 1(mod 4) (n + 11)/2 (n + 7)/2 (n + 5)/2 n ≡ 2(mod 4) (n + 2)/2 (n + 8)/2 (n + 6)/2 n ≡ 3(mod 4) (n + 11)/2 (n + 5)/2 (n + 3)/2 Consequently, if we connect with an edge the vertices u1 and v4 we obtain an edge with a weight that complements the set of weights on the concatenation of these graphs. Therefore, the graph G is 107 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 Different α-labeled alternatives for the graph G4 σ 1 2 3 n ≡ 0(mod 4) n ≡ 1(mod 4) n ≡ 2(mod 4) n ≡ 3(mod 4) 4 0 1 2 v4 u4 2 4 3 0 3 0 2 4 1 4 3 0 4 1 5 2 0 v4 u4 3 4 0 2 5 3 2 5 4 0 2 3 0 1 5 5 3 4 0 1 6 v4 u4 3 1 2 6 5 0 4 3 5 0 2 6 2 3 1 6 4 0 graceful. Furthermore, when n is even, G and its labeling are bipartite, which implies that G is indeed an α-graph. The boundary value of this α-labeling is λ = n+2 2 when n ≡ 0(mod 4) and λ = n+6 2 when n ≡ 2(mod 4). In the previous section we study how to duplicate any vertex on the spine of a caterpillar, now we analyze how to duplicate any edge on the spine. Proposition 4.3. Let G be a caterpillar of diameter at least three. An α-graph is obtained by duplicating any edge on the spine of G. Proof. Let e = v1v2 be any edge on the spine of G; thus, G−e has two components that are caterpillars on their own. We denote these components by G1 and G2 and assume that vi ∈ V (Gi) and ni is the size of Gi. We know that there exists an α-labeling fi of Gi, with boundary value λi, such that f1(v1) = λ1 and f2(v2) = n2. If H is the graph that result of the duplication of e, then H can be seen as the chain graph obtained using G1, C4, and G2 in this specific order. To generate an α-labeling of H we proceed as follows. The function f1 is transformed into a (n2 + 5)-graceful labeling; this new labeling uses the labels in {0, 1, . . . ,λ1} ∪ {n2 + λ1 + 5,n2 + λ1 + 6, . . . ,n1 + n2 + 4} and induces the weights in {n2 + 5,n2 + 6, . . . ,n1 + n2 + 4}. The labeling f2 is shifted λ1 + 2 units; thus, the new labeling of G2 uses the labels in {λ1 + 2,λ1 + 3, . . . ,n2 + λ1 + 2} and induces the weights in {1, 2, . . . ,n2}. The α-labeling of C4 is the one that assigns the labels 0, 4, 1, 2 to the consecutive vertices; this labeling is transformed into a (n2 + 1)-graceful labeling shifted λ1 units. Hence, the new labels are λ1,n2 +λ1 + 4,λ1 + 1 and n2 +λ1 + 2, respectively; the induced weights are {n2 + 1,n2 + 2,n2 + 3,n2 + 4}. Note that the weights on the edges of the union of these three graphs form the set {1, 2, . . . ,n1 + n2 + 4}, where n1 + n2 + 4 is the size of H, and the labels are in {1, 2, . . . ,n1,n2 + 4}, being λ1 and n2 + λ1 + 2 the only labels used twice. So, to form the graph H we identify the vertices labeled λ1 of G1 and C4 and the vertices labeled n2 + λ1 + 2 of G2 and C4. Since all the labelings used are bipartite, the final labeling of H is in fact an α-labeling. 108 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 An important characteristic of this labeling of H is that its boundary value is assigned either on a leaf maximum of eccentricity or on a vertex adjacent to a leaf of maximum eccentricity. Therefore, we can create a chain graph using multiple graphs similar to H, that is, built in the same way, to produce an α-graph that is the result of duplicating multiple edges of the spine of a caterpillar. Thus, we have the following corollary. Corollary 4.4. Let G be a caterpillar of diameter at least three. An α-graph is obtained by duplicating any number of edges on the spine of G. In Figure 4 we show an example of this corollary, where the four edges on the spine of a caterpillar of size 12 have been duplicated. 0 1 2 3 4 5 6 7 8 9 10 11 24 22 21 19 17 15 16 14 12 Figure 4. α-labeling of a graph obtained by duplicating some edges of a caterpillar 5. Connecting multiple copies of an α-graph Some authors used G�H to represent the traditional Cartesian product of the graphs G and H, the reason for this notation is based on the fact that a given edge uv ∈ E(G) induces a square in G×H. In this section we present a graph obtained with r copies of a graph G, that could be written as G ./ Pr. The r-tie of a graph G, is the graph H obtained with r copies of G, say G1,G2, . . . ,Gr, where every vertex in Gi is adjacent to all the vertices adjacent to its copy in Gi+1. More formally, for each i ∈ {1, 2, . . . ,r}, let Gi be a copy of a graph G of order m and size n, where V (Gi) = {vi1,vi2, . . . ,vim}; assuming that vi+1k is the copy of v i k in Gi+1, we say that a graph H is the r-tie of G if V (H) = ∪ r i=1V (Gi) and E(H) = ∪ri=1E(Gi) ∪{u i jv i+1 k : 1 ≤ i ≤ r − 1 ∧u i jv i k ∈ E(Gi)}. Thus, we have that H is a graph of order rm and size n(3r − 2) that can be decomposed into 3r − 2 copies of G. In the next theorem we prove that when G is an α-graph, any r-tie of G is also an α-graph. Theorem 5.1. If G is an α-graph, then for each r ≥ 2 the r-tie of G is also an α-graph. Proof. Suppose that G is an α-graph of order m and size n with stable sets A and B. Then, there exists an α-labeling f of G that assigns the label 0 to a vertex of A; this implies that the boundary value of f is at least λ = |A| − 1. Let H be the r-tie of G, where r ≥ 2; if V (G) = {v1,v2, . . . ,vm}, then V (Gi) = {vi1,vi2, . . . ,vim} where Gi is the ith copy of G in H and 1 ≤ i ≤ r. Consider the following labeling of the vertices of H: g(vij) = { (3r − 2)f(vj) + (i− 1) if f(vj) ≤ λ, (3r − 2)f(vj) + 2(i− 1) if f(vj) > λ. 109 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 Note that the first part of this function is strictly increasing, while the second part is strictly de- creasing. Moreover, when f(vj) ≤ λ, we get that min{g(vij) : 1 ≤ i ≤ r} = 0 and max{g(v i j) : 1 ≤ i ≤ r} = (3r−2)λ+r−1. When f(vj) > λ, we get that min{g(vij) : 1 ≤ i ≤ r} = (3r−2)(λ+ 1)−2(r−1) = (3r − 2)λ + r and max{g(vij) : 1 ≤ i ≤ r} = (3r − 2)n− 2(1 − 1) = n(3r − 2). Hence, g is an injective function with range in the interval [0,n(3r − 2)]. If A is the stable set of H that contains the vertex labeled 0 by g, then the largest label on a vertex of A is Λ = (3r − 2)λ + r − 1. Now we turn our attention to the weights induced by g on the edges of H. Let vavb ∈ E(G) such that f(vb) − f(va) = w, where w ∈ {1, 2, . . . ,n}. Then, g(vib) = (3r − 2)f(vb) − 2(i − 1), g(v i a) = (3r − 2)f(va) + (i− 1), g(vi+1b ) = (3r − 2)f(vb) − 2i, and g(v i+1 a ) = (3r − 2)f(va) + i. Therefore, g(vib) −g(v i a) = (3r − 2)(f(vb) −f(va)) − 3(i− 1) = (3r − 2)w − 3i + 3, g(vib) −g(v i+1 a ) = (3r − 2)(f(vb) −f(va)) − 3i + 2 = (3r − 2)w − 3i + 2, g(vi+1b ) −g(v i a) = (3r − 2)(f(vb) −f(va)) − 3i + 1 = (3r − 2)w − 3i + 1, g(vi+1b ) −g(v i+1 a ) = (3r − 2)(f(vb) −f(va)) − 3i = (3r − 2)w − 3i. In other terms, these four weights form the set Wi = {(3r−2)w−3i+k : 0 ≤ k ≤ 3}, where 1 ≤ i ≤ r−1 and ∪r−1i=1 Wi = [(3r − 2)w − 3(r − 1), (3r − 2)w]. Taking the union of these intervals over all the values of w, we get ∪nw=1[(3r − 2)w − 3(r − 1), (3r − 2)w] = [1,n(3r − 2)]. Thus, the set of weights induced by g on the edges of H is {1, 2, . . . ,n(3r − 2)}. Therefore, g is a bipartite graceful labeling, in other terms, g is an α-labeling of H with boundary value Λ. In Figure 5 we show an example of this labeling method for G ∼= C8 and r = 3. 24 26 28 31 33 35 45 47 49 52 54 56 0 1 2 7 8 9 14 15 16 21 22 23 Figure 5. α-labeling of the 3-tie of C8 6. k-vertex amalgamation The k-vertex amalgamation is the process that allows us to construct a new graph starting with two graphs G1 and G2 each of order at least k, where k selected vertices from each graph are merged. Note that if two adjacent vertices from G1 are amalgamated with two adjacent vertices from G2 we obtain a 110 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 multigraph. In the context of this work, the k vertices on each set are pairwise non-adjacent, in this way, we can be sure that the outcome of the amalgamation is indeed a graph, that is, there are no multiple edges present. Lemma 6.1. For i = 1, 2, let Γi be a tree with stable sets Ai and Bi. If Γi admits an α-labeling, then there exists an α-graph obtained amalgamating k vertices of B1 with k vertices of B2, where 1 ≤ k ≤ min{|B1|, |B2|}. Proof. For i = 1, 2, assume that Γi is an α-tree of size ni with stable sets Ai and Bi, where |Ai| = ai and |Bi| = bi. Any graph obtained via k-vertex amalgamation of Γ1 and Γ2 is bipartite of size n1+n2 and order n1 +n2 +2−k, where 1 ≤ k ≤ min{b1,b2} is the amount of pairs of vertices amalgamated. Since Γi is an α- tree, there exists an α-labeling fi of Γi that assigns the label 0 to a vertex of Ai. The labeling f2 is shifted a1+k−1 units; thus, the set of new labels is L2 = {a1+k−1,a1+k,. . . ,a1+a2+k−2}and the set of induced weights is still W2 = {1, 2, . . . ,n2}. The labeling of Γ1 is transformed into a (n2 + 1)-graceful labeling. Hence, the set of labels on the vertices of Γ1 is now L1 = {0, 1, . . . ,a1−1}∪{n2+a1,n2+a1+1, . . . ,n1+n2} and the set of induced weights is W1 = {n2 + 1,n2 + 2, . . . ,n1 + n2}. Note that W1∪W2 = {1, 2, . . . ,n1 +n2} and that L1∩L2 = {n2 +a1,n2 +a1 + 1, . . . ,n2 +a1 +k−1}, i.e., a set of cardinality k formed by consecutive integers. So, identifying the vertices of B1 and B2 with the same label we obtain a graph with an α-labeling. In Figure 6 we show an example of the construction presented in this lemma, where Γ2 has size 9, a2 = 6, b2 = 4, Γ1 has size 10, a1 = 5, b1 = 6, the graph on the left side corresponds to the amalgamation of k = 4 vertices while the graph on the right side is obtained with k = 3. Γ1 : 0 1 2 3 4 5 9 8 7 6 Γ2 : 10 9 8 7 6 5 0 1 2 3 4 k = 4 : 8 9 10 11 12 13 19 18 17 16 15 14 0 1 2 3 4 k = 3 : 7 8 9 10 11 12 1319 18 17 16 15 14 0 1 2 3 4 Figure 6. α-labelings of some k-vertex amalgamations of two α-trees The core of the proof of this lemma can be found on the fact that the labels on a stable set of an α-labeled tree are consecutive integers; this characteristic is also present in the α-labelings of some other graphs like complete bipartite graphs and some cycles. In particular, the well-known α-labeling of the cycle C4n assigns consecutive integers to the elements of one stable set, therefore, it can be used in the context of this lemma. When Γ1 = Γ2 = C4n, the edge amalgamation of the 2n vertices of one stable set results in a graph H that can be understood as well as the supersubdivision of every edge of C2n where each edge of this last cycle is replaced by a copy of C4 ∼= K2,2. Summarizing, using this lemma together with the α-labeling of C4n given by Rosa in [14], we can prove the following theorem. Theorem 6.2. Let n ≥ 2, if every edge of the cycle C2n is supersubdivided, that is, replaced by K2,2, the resulting graph admits an α-labeling. 111 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 In Figure 7 we show two examples of this construction for the cycles C4 and C6. 16 15 1413 0 8 1 9 311 4 12 24 23 22 212019 0 12 1 13 2 14 416 5 17 6 18 Figure 7. α-labelings of a supersubdivision of C4 and C6 A quadrangular cactus is a connected graph all of whose blocks are squares (the cycle C4 ∼= K2,2) and the block-cutpoint graph is a tree. The lemma also allows us to prove the existence of an α-labeling for a family of quadrangular cacti. Theorem 6.3. If T is an α-tree such that all the vertices of one stable set have degree two, then the quadrangular cactus obtained by duplicating all these vertices is an α-graph. Proof. To obtain an α-graph from T we just need to apply the construction in Lemma 6.1, where Γ1 ∼= Γ2 ∼= T and the α-labeling of T is one that assigns the largest label to the vertices of the stable set containing no interior vertices. The fact that each vertex in this stable set has degree two guarantees the obtainment of a square, for every subpath u1 −v −u2, where v is the vertex of degree two. We show an example of a quadrangular cactus in Figure 8, which α-labeling was attained following the procedure of Lemma 6.1. We must observe here that the condition that states that the degree must be two can be dropped, the resulting graph is still an α-graph but it is not a cactus. 9 10 11 12 13 14 15 16 25 2627 28 29 30 31 32 0 1 2 3 4 5 6 7 8 Figure 8. α-labeling of a quadrangular cactus built on an α-tree We conclude this work with another application of Lemma 6.1. The m × n grid is the Cartesian product G = Pm × Pn. Assuming that the vertices of this graph have integer coordinates, a cell of G is the subgraph induced by the vertices (i,j), (i + 1,j), (i + 1,j + 1), and (i,j + 1). This graph can be understood as a sequence of vertex amalgamations of paths. In particular, if t ≥ 0, the grid Pm ×Pm+t is obtained with the sequence of paths H1,H2, . . . ,H2m+t−2, where 112 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 Hi ∼=   P2i+1 if 1 ≤ i ≤ m− 1, P2m if m ≤ i ≤ m + t− 1, H2m+t−1−i if m + t ≤ i ≤ 2m + t− 2, where all the vertices in the largest stable set of the ith term of the sequence are amalgamated with all the vertices in the smallest stable set of the (i + 1)th term. In other words, an α-labeling of G can be obtained applying the method of Lemma 6.1 to this sequence of paths. This labeling does not correspond with the α-labeling of the grid given by Jungreis and Reid [8]. In [4], Barrientos and Minion introduced the concept of analogous caterpillars. The caterpillars G1 and G2 are said to be analogous if the stable sets of G1 have the same cardinality as the stable sets of G2. Suppose that for each i ∈ {1, 2, . . . , 2m + t− 2}, Gi is analogous to the path Hi defined above. We say that G is an irregular grid of order m× (m + t) if G is obtained from Pm ×Pm+t by replacing the subgraph Hi by an analogous Gi. Note that G is also a bipartite graph where all the cells are copies of C4 too. We claim that all irregular grids are α-graphs. Theorem 6.4. All irregular grids are α-graphs. Proof. Suppose that G is an irregular grid of order m× (m + t) built with the sequence of subgraphs G1,G2, . . . ,G2m+t−2. We assume that the stable set Bi of Gi has the same cardinality that the stable set Bi+1 of Gi+1 and that all the vertices in Bi and Bi+1 are amalgamated. Since each of these subgraphs is a caterpillar, there exists an α-labeling for each of them. For every 2 ≤ i ≤ 2m + t − 2, we apply the lemma with Γ2 = Gi and Γ1 being the graph obtained with G1,G2, . . . ,Gi−1. When this process is concluded we have an irregular graph with an α-labeling as claimed. In Figure 9 we present an example of an irregular grid of order 6 × 6 which α-labeling is obtained using the procedure described in the last theorem. 0 2 3 4 8 9 10 11 12 18 19 20 21 22 26 27 28 30 60 59 56 55 54 53 48 47 46 45 44 43 38 37 36 35 32 31 Figure 9. α-labeling of an irregular grid Acknowledgment: I would like to thank the referee for his/her valuable comments and suggestions. 113 C. Barrientos / J. Algebra Comb. Discrete Appl. 9(2) (2022) 101–114 References [1] C. Barrientos, S. Barrientos, On graceful supersubdivisions of graphs, Bull. Inst. Combin. Appl. 70 (2014) 77–85. [2] C. Barrientos, S. Minion, Alpha labelings of snake polyominoes and hexagonal chains, Bull. Inst. Combin. Appl. 74 (2015) 73–83. [3] C. Barrientos, S. Minion, New attack on Kotzig’s conjecture, Electron. J. Graph Theory Appl. 4(2) (2016) 119–131. [4] C. Barrientos, S. Minion, Snakes and caterpillars in graceful graphs, J. Algorithms and Comput. 50(2) (2018) 37–47. [5] G. Chartrand, L. Lesniak, Graphs & digraphs, 4th Edition. CRC Press, Boca Raton (2005). [6] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2020) #DS6. [7] S. W. Golomb, How to number a graph, R. C. Read (Editor), Graph theory and computing, Academic Press, New York (1972) 23-37. [8] D. Jungreis, M. Reid, Labeling grids, Ars Combin. 34 (1992) 167–182. [9] V. J. Kaneria, S. K. Vaidya, G. V. Ghodasara, S. Srivastav, Some classes of disconnected graceful graphs, Proc. First Internat. Conf. Emerging Technologies and Appl. Engin. Tech. Sci. (2008) 1050– 1056. [10] A. Kotzig, On certain vertex valuations of finite graphs, Util. Math. 4 (1973) 67–73. [11] S. C. López, F. A. Muntaner-Batle, Graceful, harmonious and magic type labelings: relations and techniques, Springer (2017). [12] M. Maheo, H. Thuillier, On d-graceful graphs, Ars Combin. 13 (1982) 181–192. [13] G. Ringel, Problem 25, in: Theory of graphs and its applications, Proc. Symposium Smolenice 1963, Czech. Acad. Sci., Prague, Czech. (1964) 162. On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966) [14] A. Rosa, On certain valuations of the vertices of a graph, theory of graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach NY and Dunod Paris (1967) 349–355. [15] A. Rosa, Labelling snakes, Ars Combin. 3 (1977) 67–74. [16] A. Rosa, J. Širáň, Bipartite labelings of trees and the gracesize, J. Graph Theory 19(2) (1995) 201–215. [17] G. Sethuraman, P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math. 32 (2001) 1059–1064. [18] P. J. Slater, On k-graceful graphs, Proc. of the 13th S. E. Conf. on Combinatorics, Graph Theory and Computing (1982) 53–57. [19] B. Yao, X. Liu, M. Yao, Connections between labellings of trees, Bull. Iranian Math. Soc. 43(2) (2017) 275–283. 114 https://mathscinet.ams.org/mathscinet-getitem?mr=3204924 https://mathscinet.ams.org/mathscinet-getitem?mr=3204924 https://mathscinet.ams.org/mathscinet-getitem?mr=3363625 https://mathscinet.ams.org/mathscinet-getitem?mr=3363625 http://dx.doi.org/10.5614/ejgta.2016.4.2.1 http://dx.doi.org/10.5614/ejgta.2016.4.2.1 http://dx.doi.org/10.22059/JAC.2018.69503 http://dx.doi.org/10.22059/JAC.2018.69503 https://www.worldcat.org/title/graphs-digraphs/oclc/55510638 https://doi.org/10.37236/27 https://doi.org/10.1016/B978-1-4832-3187-7.50008-8 https://doi.org/10.1016/B978-1-4832-3187-7.50008-8 https://mathscinet.ams.org/mathscinet-getitem?mr=1206560 https://mathscinet.ams.org/mathscinet-getitem?mr=384616 https://link.springer.com/book/10.1007/978-3-319-52657-7 https://link.springer.com/book/10.1007/978-3-319-52657-7 https://mathscinet.ams.org/mathscinet-getitem?mr=666937 https://doi.org/10.1002/jgt.3190190207 https://doi.org/10.1002/jgt.3190190207 https://mathscinet.ams.org/mathscinet-getitem?mr=1846112 https://mathscinet.ams.org/mathscinet-getitem?mr=1846112 http://bims.iranjournals.ir/article_930.html http://bims.iranjournals.ir/article_930.html Introduction The essential results Duplicating vertices Duplicating edges Connecting multiple copies of an -graph k-vertex amalgamation References