Abstract-Let G(p,q) be a simple graph, where p is the number of vertices and q is the number of edges if there exists a one-to-one mapping/: so that for any two vertices uveE(G), if d(u)=d(ý), then S(u)=S(y), where and d(u) represents the degree of vertex w,/ is called the Adjacent Vertex Reducible Edge Labeling (AVREL) of G. Building on the current graph labeling algorithm, a heuristic search algorithm is designed, and this algorithm is used to label random graphs with less than 12 vertices and obtain the result set of adjacent vertex reducible edge labeling. Based on the analysis of the result set and combining it with the known theorem, the adjacent vertex reducible edge labeling law of other compound graphs is obtained, and the related proof is given.
Index Terms-Adjacent Vertex Reducible Edge Labeling, special graphs, compound graphs, algorithm
I. Introduction
IN the mid-1960s, the problem of graph labeling first emerged, becoming one of the most focused research topics in the field of graph theory. In 1967, Rosa et al.[1] put forward a beautiful conjecture that "every tree is beautiful.". In 1997, Burris et al.[2] put forward the idea of vertex-distincting edge coloring along with associated conjectures. In 2002, MacDougall et al.[3] proposed the vertex-magic total labeling, which has since attracted increasing attention and research from scholars. In 2007, the literature[4] made new progress in the study of graceful labeling, super-magic total labeling, and harmonic labeling, and successfully proved the related conjecture. In 2009, Zhang Zhongfu et al.[5] expanded on the idea of distinguishing coloring by introducing the concept of reducible coloring. Many scholars have since studied this concept, leading to a series of research finding[6][7]. In 2023, the literature[8] expanded on the theory of adjacent vertex-reducible edge labeling, deriving theorems and conjectures for path graphs, cycle graphs, star graphs, fan graphs, wheel graphs, tree graphs, and their compound graphs. The correctness of these theorems and conjectures was verified using mathematical proofs and computational algorithms.
In frequency allocation, to reduce interference between base stations and users, it is necessary to ensure that different frequencies are assigned to different base stations. This issue can be expressed as a graph theory problem by abstracting the network topology into an undirected graph, where base stations are represented as vertices, and channels between them as edges. The issue of channel frequency allocation is then transformed into the problem of labeling the edges associated with each vertex in the graph, with the condition that each edge receives a different labeling. Building on the research of various scholars, this paper presents an algorithm for adjacent vertex reducible edge labeling, based on concepts such as vertex sum reducible edge coloring[9][10], adjacent vertex distinguishable edge coloring[11], and vertex magic total labeling[12]. This algorithm aims to address the adjacent vertex reducible edge labeling problem for special and compound graphs, starting with reducible coloring and incorporating vertex magic total labeling. The algorithm's labeling results are analyzed, corresponding theorems are summarized, and proofs are offered.
II. Preliminary Knowledge
Definition 1: Let G(K,E) be a simple graph. If there exists one-to-one mapping / Z7(C7)^-{1,2,...so that for any two vertices uveE(G), if d(u)=d(v), then S(u)=S(v), where S(uy^MWeE(G^uw) and d(u) represents the degree of vertex u, then/is called the Adjacent Vertex Reducible Edge Labeling (A VREL) of G. The graph G is termed A VREL graph; otherwise, it is referred to as non-AVREL graph.
Definition 2: Let G\ and Gi be simple connected graphs belonging to the path graph (Pn), cycle graph (Cn), star graph (Sn), fan graph (Fn), wheel graph (Wk) and complete graph (Kn) where symbol a represents center nodes of star, fan and wheel graphs, degree-1 vertices of path graph and any vertices. Symbol b represents non-center nodes of star and wheel graphs, degree-2 vertices of fan graphs, and degree-2 vertices of path graphs. Symbol d represents nodes at a distance of 2 from the previous node without passing through the center node. The compound graph gy G2 refers to connecting the a node of Gx to the a node of G^ as shown in Fig. 1.
Definition 3: Let Gn be a simple graph. The compound graph Gn Gn(n>3) refers to the Gn formed by sharing edges with itself, as shown in Fig. 2(a).
Definition 4: The friendship graph Tn is the compound graph formed by n copies of the cycle graph Сз with common vertices, as shown in Fig. 2(b).
Definition 5: Let Gx and G2 be two simple graphs with the number of vertices nx and ni and the number of edges mi and m2, respectively. We define the corona graph of Gx and G2 as a graph that connects each vertex of Gx to each vertex of a copy of G2, represented as о G2. The vertex number of Gx о G2 is и/1 + n2), and the edge number is + nxn2 + nxm2. For example, Gx = C4, G2 = P2, and the corona graph of vertex C.p of graph Gx and G2 are shown in Fig. 3.
Definition 6: Let Gi and G2 be two simple graphs with the number of vertices nx and П2, and the number of edges mi and m2. The generalized corona graph of Gx and G2 is defined as follows: for each b node of Gx (where b represents non-center nodes of star, wheel, friendship graphs, degree-2 vertices of fan graphs, and degree-2 vertices of path graphs), connect it to copy of the a node of G2 (where a represents center nodes of star, fan, wheel, friendship graphs, degree-1 vertices of path graphs, and any vertices of cycle graphs). This results in a compound graph denoted as o G" * When several nodes of Gx are connected with a nodes of G2, the generalized corona graph is abbreviated as Gfc °G2 * For example, G, = W. and G, = S., the generalized corona graph as wb o Sa 18 2 3 8 3 of graphs Gx and G2, as shown in Fig. 4.
III. Avrel Algorithm
A. Preparation phase
Based on the definition of AVREL, a graph classification function is defined using the graph's degree sequence. The graph is divided into two classes: the graph with the same degree sequence of neighboring vertex and the other with a different degree sequence of neighboring vertex; the adjacent vertex degree sequence has the same labeling, and the labeling number is continuous. A balance function is then defined according to the labeling conditions of AVREL, and this balance function is used to determine whether the labeling meets the necessary conditions.
The basic principles of the AVREL algorithm involve utilizing permutations to generate a solution space and recursively searching the solution space to obtain labeling that satisfyingly restrictive condition.
(1) Generate the solution space based on the preparatory work and recursively search through it.
(2) Use a balancing function to filter out graph sets that satisfy AVREL conditions and output the labeling results as an adjacency matrix.
(3) We classify the graph sets as AVREL if they satisfy the condition, and as non-AVREL if they don't.
We are setting the labeling balance constraint condition based on the principles of the AVREL algorithm:
(1) ..., and k is a constant.
(2) A one-to-one mapping ... exists, and the labeling numbers are consecutive.
B. Pseudocode for A VREL Algorithm
C. Analysis of Experimental Results
Table I lists the number of A VREL graphs in the single circle and double circle graphs, ranging from 4 to 12 vertices. From Table I, it can be seen that the larger the vertices are, the proportion of single circle graphs that satisfy A VREL graphs increases gradually, and when the vertices are 8, the proportion reaches the maximum, and tends to be smooth after that; double circle graphs are exactly the opposite, and when the number of vertices is 8, the proportion of double circle graphs that satisfy A VREL graphs decreases and tends to be smooth after that. After that, it tends to stabilise.
In Fig. 5, we conducted experiments on all random graphs, ranging from 4 to 12 vertices. All random graphs within the range of 4 to 12 vertices exhibit a proportion of A VREL and non-AVREL graphs. We can observe that the proportion of the A VREL graph gradually increases, reaches its maximum when there are 8 vertices, and then gradually decreases.
IV. Theorems And Proofs
Theorem 1: The generalized corona graph ... ° ( = l(mod 2),m = 0(mod 2),и > 3) is A VREL graph.
Proof: Let the vertex set be ...
When n = l(mod 2fm = 0(mod 2) and n > 3 , the adjacent vertex reducible edge labeling of the generalized corona graph is:
...
At this point, the graph contains degree-1 vertices, degree-и vertices, and degrec-(m+3) vertices. Since the degree-1 and degree-и vertices are not adjacent, they do not need to be considered. It is only necessary to ensure that all adjacent degree-(m+3) vertices have the same sum of labeling, ... are adjacent degrec-(m+3) vertices. When 2 < i < 2k, the sum of their labels:
...
The symbol "||" in the full text is represented as a logical or.
An example of the generalized corona graph о Sļ is shown in Fig. 8.
...
According to the A VREL definition, the function ... is a one-to-one mapping, and the sum of edge labels for adjacent vertices of the same degree is constant. The proof of Theorem 1 is complete.
Theorem 2: The generalized corona graph is
A VREL graph.
Proof: Let the set of vertex be V^Wz^ = and the set of edge be ...
The adjacent vertex reducible edge labeling of the generalized corona graph P1 is:
...
...
Currently, the figure contains degree-1 vertices, degree-4 vertices, and degree-и vertices. The degree-1 vertices are not adjacent, and the degree-и vertices form a separate point, so they are not considered. It is only necessary to ensure that all adjacent degree-4 vertices have the same sum of labels, ... are adjacent degree-4 vertices. When 2<i<2k, the sum of their labels:
...
A graphical example of the generalized corona graph Wb oP" is shown below in Fig. 9. П 2 О
As defined by A VREL, it is possible to determine the
function of the one-to-one mapping of ...
, and the sum of edge labels for
adjacent vertices of the same degree is constant. The proof of Theorem 2 is complete.
Theorem 3: For generalized corona graph CS^ (n>3,m>2) except ... , all are A VREL graph.
Proof: Let the vertex set of the generalized corona graph ...
Case 1: When n,m = l(mod 2) , the adjacent vertex reducible edge labeling of the generalized corona graph CaoSa is: n m
Let ...
When n,m = l(mod 2) , an example of the generalized corona graph C" is shown in Fig. 10.
In the graph, there are only degree-1 and degree-(m+2) vertices. One of the degree-1 vertices is not adjacent, so there is no need to consider it, only to ensure that the adjacent degree-(m+2) vertices are the same. Meanwhile, ^ui, u2, .... un^ are adjacent degree-(m+2) vertices in the graph. When 1 < i < n , the sum of their labels is as follows:
...
From the proof above, it can be determined that for the generalized corona graph Can о 8^п>3,т>2) when 7z,m = l(mod 2), for adjacent vertices with the same degree, the total of their edge labels is constant. According to the A VREL definition, case 1 is proven to be an A VREL graph.
Case 2: When m = 0(mod 2) , the adjacent vertex reducible edge labeling of the generalized corona graph
Let ...
When m = 0(mod 2) , an example of the generalized corona graph C" о Sļ is shown in Fig. 11.
In the graph, there are degree-1 and degree-(m+2) vertices. One of the degree-1 vertices is not adjacent, so there is no need to consider it, only to ensure that the adjacent degree-(m+2) vertices are the same. Meanwhile, ui, ..., un^ are adjacent degree-(m+2) vertices in the graph. When 1 < z < и , the sum of their labels:
...
It can be determined by the above proof that the total of the edge labeling of the adjacent vertices with the same degree is constant for the generalized corona C>S>>3,m>2^ when m = 0(mod 2). According to the A VREL definition, case 2 is a proof of the A VREL graph.
In summary, the functions of one-to-one mapping for f ( E ( Can o S" j ) {1,2, * * *, n + nm\ can be determined from case 1 and case 2, and the total of the edge labeling of adjacent vertices with the same degree is a constant. According to the A VREL definition, Theorem 3 proved.
Theorem 4: The generalized corona graph F^ °s^mE 0(mod 2)) is AVREL graph.
Proof: Let the vertex set be ... and the edge set be
...
When m = 0(moć/2) the adjacent vertex reducible edge labeling of the generalized corona graph F^bc Fļ is:
Let ...
For the generalized corona graph F^oSam, its example
graph is shown in Fig. 12.
There are degree-1, degrce-(m+2), degree-(m+3), and dcgree-(m+n) vertices that are not adjacent, so there is no need to consider them, only to ensure that the adjacent dcgree-(m+3) vertices are the same. Meanwhile, ... are adjacent degree-(m+3) vertices in the graph. When 2 < i < n -1, the sum of their labels:
Case 1: When n = 0(mod 2)
...
According to the AVREL definition, the function can be determined to establish a one-to-one mapping for ..., and the edge label
sum for adjacent vertices of identical degrees is constant. Theorem 4 roved.
Theorem 5: The compound graph ... is AVREL graph.
Proof: Let ... be the vertex set of the compound graph
The central vertices are denoted by {ui, ui, .uj, and the initial labels of the non-central vertex in the first graph corresponds to the vertex connected to it in the second graph. Similarly, the initial label of the non-central vertex in the second graph corresponds to the vertex connected to it in the first graph, and so on.
An example graph of the compound graph ... is shown in Fig. 13.
...
When ... is:
Let t ...
The graph has degree-3, degree-6, and degree... vertices. Specifically, degree... and
degree-6 vertices are not adjacent, so they are not considered. One need only match the labels of adjacent degree-3 vertices on each cycle graph are the same. The set {vf2,vf3,-,v^}
represents adjacent degree-3 vertices. When 2</<^, the sum of their labels is:
Case 1: When ...
...
According to the AVRET definition, the one-to-one mapping function ...
... can be determined, and the total of edge labels for adjacent vertices with identical degrees remains constant. This concludes the proof of Theorem 5.
Theorem 6: The compound graph ... is AVRET graph.
Proof: Let the vertex set be ... and the set of edge be =
... of the compound graph 4 7^ . In which, the central nodes are ..., and the edge v^vn of the first wheel graph is connected to the edge V277V21 of the second wheel graph.
Case 1: When ..., the adjacent vertex reducible edge labeling of the compound graph ... is:
...
When n = 0(mod 2^ , the example graph of compound graph Wn ‡ Wn is shown in Fig. 14.
The graph contains degree-3, degree-5, and degree-и vertices. Since the degree-и vertices are not adjacent, they do not need to be considered. It is only necessary to ensure that the sum of the labels for the two adjacent degree-5 vertices and others for each adjacent degree-3 vertex in the wheel graph is the same. In the graph, vn/v2i and vih/v2h are adjacent degree-5 vertices, and {v^, ж ..., is an adjacent degree-3 vertex. When 2 < i < t^n -1), their sum of labels is:
...
Case 2: When n = \(mod 2), the adjacent vertex reducible edge labeling of the compound graph ... is:
...
When ..., the example graph of compound graph Wn Ф Wn is shown in Fig. 15.
The graph has degree-3, degree-5, and degree-и vertices. Among them, the degree-и vertices are non-adjacent, so they need not be considered. On each wheel graph, it is only necessary to ensure that adjacent pairs of degree-5 vertices share the same labels as adjacent degree-3 vertices. vi(„-i)/v2(«-i) and are adjacent degree-5 vertices, and {vn, va, ..., w<>2)} are adjacent degree-3 vertices. When 1 < z < / (и - 2), the sum of their labels is:
...
According to the A VREL definition, the one-to-one mapping function f{E(Wn {1,2,-,4и} can be determined, and the sum of the edge labels for adjacent vertices of the same degree is constant. The proof of Theorem 6 is complete.
Theorem 7: The generalized corona graph ° ^m{m = Ujnod 2)) is A VREL graph.
Proof: Let the vertex set be U
An example graph of generalized corona graph ° sļ is shown in Fig. 16.
When m = l(mod2), the adjacent vertex reducible edge labeling of the generalized corona graph is:
Let ...
The graph has degree-1, degree-(m+2), and degree-2^ vertices. Among them, the degree-1 and degree-2/2 vertices are non-adjacent, so they do not need to be considered. It is only necessary to ensure that the labels of the two adjacent degree-(m+2) vertices are the same, {vi, v2, .v2n} are adjacent degree-(m+2) vertices, and when 1 < z < 2/?, the sum of their labels is:
Case 1: When z = \(mod 2)
...
Case 2: When z = O^mod 2)
It is possible to determine a function that establishes a one-to-one mapping for ... according to the A VREL definition, and the total of edge labels for adjacent vertices with identical degrees remains constant. The proof of Theorem 7 is complete.
Theorem 8: The corona graph tfo(c3TpA (/7 = l(mod 2)) is A VREL graph.
Proof: Let the vertex set of corona graph Wn o^C3 Taa P2) be о ^C3 Taa Д - (zip U {Eí'Ei"· "^«4} and the edge set be ...
When /2 = l(mod 2) , the adjacent vertex reducible edge labeling of the corona graph Wn о (c3 Ťaa Д ) are labeled:
...
...
The graph has degree-2, degree-3, degree-4, degree-7, and degree-^ vertices. Moreover, there are degree-3 vertices and degree-7 vertices in the adjacent same degree vertices, so degree-2, degree-4 and degree-72 vertices need not be considered, just make sure that the adjacent degree-3 vertices are the same as the adjacent degree-7 vertices on corona graph. In the graph, ... and ... are adjacent degree-3 vertices and degree-7 vertices, the sum of their labels is:
...
According to the A VREL definition, it is possible to determine that the one-to-one mapping function ... and the sum of the edge
labels for adjacent vertices of the same degree are constant. This concludes the proof of Theorem 8.
V. Conclusion
This paper designs a novel adjacent vertex reducible edge labeling algorithm to address the signal interference problem in frequency allocation, based on existing approaches like vertex sum reducible edge coloring, adjacent vertex distinguishable edge coloring, and vertex magic total labeling. The algorithm iteratively finds the optimal solution, labeling path graphs, circle graphs, star graphs, fan graphs, wheel graphs, friendship graphs, and their compound graphs within a finite number of vertices. When a graph G(K, E) satisfies certain conditions, such graphs have A VREL labeling patterns, according to analysis. We derive the labeling patterns, summarize the theorems, and provide relevant proofs.
Manuscript received January 20, 2024; revised September 19, 2024.
This work was supported by the National Natural Science Foundation of China (No. 11961041, 62262038), the Key Project of Natural Science Foundation of Gansu Province, China (No. 24JRRA222) and the Gansu Provincial Science and Technology Plan Project (No. 21ZD8RA008).
Liangjing Sun is a postgraduate student at the School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou, Gansu, 730070, China, (e-mail: [email protected]).
Jingwen Li is a professor at the School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou, Gansu, 730070, China, (corresponding author to provide phone: +8613893413673; e-mail: [email protected]).
Cong Huang is a postgraduate student at the School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou, Gansu, 730070, China, (e-mail: [email protected]).
Xin Gao is a postgraduate student at the School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou, Gansu, 730070, China, (e-mail: [email protected]).
LIANGJING SUN was born in Dingxi, Gansu Province, China in 2000. She received a BA degree in information security from Gansu University of Political Science and Law in 2022.Now she is studying for an M. Phil in computer technology at Lanzhou Jiaotong University. Her major field of study is graph theory algorithm with applications.
JINGWEN LI was born in 1965. He graduated from Northeastern University with a major in computer science and technology in 1989. He is a professor and master supervisor of Lanzhou Jiaotong University. He also belongs to key Laboratory of Media convergence Technology and Communication, Gansu Province, Lanzhou, 730030, China. His main research interests include graph theory algorithm and its application.
References
[ 1 ] A. ROSA, "On certain valuations of the vertices of a graph," Theory of Graphs, pp. 349-355,1967.
[2] A C BURRIS, and R H SCHELP, "Vertex-distinguishing proper edge-colorings," Journal of Graph Theory, vol. 26, no. 2, pp. 73-82, 1997.
[3] J A MACDOUGALL, M MILLER, and WD WALLIS, "Vertex-magic total labeling of graphs" Utilitas Mathematics, vol. 61, pp. 3-21, 2002.
[4] Yue Xi, "The Research on Labelling Problems in Graph," Journal of Dalian University of Technology, 2007.
[5] Jing-Wen Li, Zhong-Fu Zhang, and En-Qiang Zhu, "Adjacent Vertex Reducible Edge-Total Coloring of Graphs," 2009 2nd International Conference on Biomedical Engineering and Informatics, IEEE, pp. 1-3, 2009.
[6] Li Wang, Jing-Wen, and Li-Jing Zhang, "Adjacent Vertex Reducible Total Labeling of Graphs" IAENG International Journal of Computer Science, vol. 50, no. 2, pp. 715-726, 2023.
[7] Li Wang, Jing-Wen Li, Chen Song, and Li-Jing Zhang, "Adjacent Vertex Reducible Total Labeling of Corona Graph" Engineering Letters, vol. 31, no. 2, pp. 618-626, 2023.
[8] Shu-Cheng Zhang, "Research on Sum Reducible Coloring and Reducible Labeling Algorithms of Random Graphs" Lanzhou Jiao tong University, 2022.
[9] Jing-Wen Li, Yu-Mei Kang, Shu-Cheng Zhang, and Ruo Luo, "The Vertex Sum Reducible Edge Coloring for Graphs" Journal of Wuhan University (Natural Science Edition), vol. 68, no. 05, pp. 487-495, 2022.
[10] Ruo Luo, Jing-Wen Li, and Shu-Cheng Zhang, "Adjacent points sum reducible edge coloring of some joint graphs" Journal of Central China Normal University (Natural Sciences), vol. 57, no. 02, pp. 201-207, 2023.
[11] Xiu-Qing Jia, "On the D(2)-Vertex Distinguishing Coloring of Some Graphs" Lanzhou Jiaotong University, 2023.
[12] Xiao-Hui Xi, Jing-Wen Li, and Shuai Sun, "Vertex-Magic Total Labelings of Some Graphs" Journal of Southwest China Normal University (Natural Science Edition), vol. 45, no. 08, pp. 18-24, 2020.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
© 2024. This work is published under https://creativecommons.org/licenses/by-nc-nd/4.0/ (the“License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Abstract
Abstract-Let G(p,q) be a simple graph, where p is the number of vertices and q is the number of edges if there exists a one-to-one mapping/: so that for any two vertices uveE(G), if d(u)=d(ý), then S(u)=S(y), where and d(u) represents the degree of vertex w,/ is called the Adjacent Vertex Reducible Edge Labeling (AVREL) of G. Building on the current graph labeling algorithm, a heuristic search algorithm is designed, and this algorithm is used to label random graphs with less than 12 vertices and obtain the result set of adjacent vertex reducible edge labeling. Based on the analysis of the result set and combining it with the known theorem, the adjacent vertex reducible edge labeling law of other compound graphs is obtained, and the related proof is given.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer