EDGE-GRACEFUL USUAL FAN GRAPHS
Aaron D.C. Angel 1 , John Rafael M. Antalan 2 ∗ , John Loureynz F.Gamurot 1 , and Richard P. Tagle 2 · 2024
Read EDGE-GRACEFUL USUAL FAN GRAPHS by Aaron D.C. Angel 1 , John Rafael M. Antalan 2 ∗ , John Loureynz F.Gamurot 1 , and Richard P. Tagle 2 (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08338.txt.
Introduction
Angel, Antalan, Gamurot, and Tagle determine which fan graphs admit a graceful edge labeling. Their paper, from twenty twenty-four, works in graph labeling theory. A fan graph joins one hub point to every point of a path. Edge-graceful means edges take the numbers one through the edge count, and the sums at each point all differ.
A classic theorem by Lo gives a divisibility test any such graph must pass. The team pairs that test with number equations and a search program. Together they pin down every edge-graceful usual fan graph. Matching labelings are given for each case. The result closes the question for this graph family.
Catalog record
| CREATOR | Aaron D.C. Angel 1 , John Rafael M. Antalan 2 ∗ , John Loureynz F.Gamurot 1 , and Richard P. Tagle 2 |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 26 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-08338
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
EDGE-GRACEFUL USUAL FAN GRAPHS Aaron D.C. Angel 1 , John Rafael M. Antalan 2 ∗ , John Loureynz F.Gamurot 1 , and Richard P. Tagle 2 Abstract . A graph G G with p p vertices and q q edges is said to be edge-graceful if its edges can be labeled from 1 1 through q q , in such a way that the labels induced on the vertices by adding over the labels of incident edges modulo p p are distinct. A known result under this topic is Lo’s Theorem, which states that if a graph G G with p p vertices and q q edges is edge-graceful, then p | ( q 2 + q − p ( p − 1 ) 2 ) p\Big|\Big(q^{2}+q-\dfrac{p(p-1)}{2}\Big) . This paper presents novel results on the edge-gracefulness of the usual fan graphs. Using Lo’s Theorem, the concepts of divisibility and Diophantine equations, and a computer program created, we determine all edge-graceful usual fan graphs F 1 , n F_{1,n} with their corresponding edge-graceful labels. Research Preprint ISSN: XXXX-YYYY Vol XX, Issue Y(202Z) 1-19 https://doi.org/ 2020 Mathematics Subject Classification Primary 05C78; Secondary (None). 1. Introduction The study of graphs is a vast field in mathematics which offers a plethora of unique and interesting topics. One of these particular topics in graph theory is graph labeling. The concept of graph labeling was first introduced in the mid-1960s. Graph labeling is an assignment of integers to the vertices or edges, or both, of a graph under certain conditions [ 1 ] . In the last 60 years, over 200 types or variations of graph labeling have been studied and about 2500 articles have been published [ 2 ] . One type of graph labeling is graceful labeling. A graceful labeling or graceful numbering is a special graph labeling of a graph on m edges in which the vertices are labeled, using a subset of distinct nonnegative integers from 0 to m and each edge of the graph is uniquely labeled by the absolute difference between the labels of the vertices incident to it. If the resulting graph edge numbers run from 1 to m inclusive, it is a graceful labeling, and the graph is said to be a graceful graph [ 3 ] . On the other hand, the concept of edge-gracefulness and edge-graceful graphs was defined and introduced by Lo in 1985 [ 4 ] . Edge-graceful labeling is considered as a reversal of graceful labeling because it labels the edges first; then the labels of the vertices would depend on the labels of the edges incident to them. That is, a graph G with p vertices and q edges is said to be edge-graceful if the edges can be labeled from 1 through q , in such a way that the labels induced on the vertices by adding over the labels of incident edges modulo p are distinct [ 3 ] . Since the introduction of the concept of edge-graceful labeling in 1985, several works on the edge-graceful labeling of specific families of graphs have been conducted. For instance, Kuan et al. [ 5 ] studied edge-graceful unicyclic graphs. Lee et al. [ 6 ] on the other hand, studied the edge-graceful labeling of complete graphs. The work of Small in [ 7 ] shows that regular (even) spider graphs are edge-graceful. In 1992, Cabannis et al. [ 8 ] studied the edge-gracefulness of regular graphs and trees. Fast-forward to 2017, Venkatesan and Sekar [ 3 ] attempted to prove that among all wheel graphs W_{n} , only W_{3} is edge-graceful while a complete proof of their result was provided recently in [ 9 ] . In this paper, we used essential graph theory concepts to study the basic properties of usual fan graphs. In particular, their vertex and edge sets were used to apply Lo’s Theorem, an initial condition that must be satisfied to conclude that a particular graph is edge-graceful. Then, using the definition of edge-graceful labeling, and some preliminary concepts in number theory, which include the concept of the Diophantine equation, this paper determined which among the said graphs satisfied Lo’s Theorem. If a particular graph does not satisfy Lo’s Theorem, then it automatically does not qualify to be an edge-graceful graph. Finally, by using a computer program that we created, this paper constructed actual examples of edge-graceful labeling of the usual fan graphs that satisfy these initial conditions, thereby showing that the graphs are indeed edge-graceful. 2. Preliminaries For completeness, we provide all the preliminary concepts and results necessary for the clear and organized presentation of the results of this study. Moreover, we emphasize that the graph-theoretical definitions used in this section, aside from the concept of edge-graceful labeling, are from Wolfram MathWorld [ 10 ] . We also refer the readers who are unfamiliar with graph theory concepts that were briefly stated in this paper, to some standard graph theory references such as Gallian’s “A Dynamic Survey of Graph Labeling” [ 1 ] and Gross’s “Graph theory and its applications” [ 11 ] . 2.1. Essential Graph Theory Concepts To begin this subsection, we briefly discuss some key concepts in graph theory that are essential to this paper. Definition 2.1 . A (p,q) -graph G(V,E) is called edge-graceful if there exist a bijection f:E\rightarrow\{1,2,....,q\} , such that the induced mapping f^{+}:V\rightarrow\mathbb{Z}_{p} , defined by f^{+}(u)\equiv\Big(\sum_{v\in N(u)}f(uv)\Big)(mod\hskip 2.84526ptp) is also a bijection, where \mathbb{Z}_{p} is the set of integers \{0,1,2,..,(p-1)\} . Moreover, every f(uv) are the labels of the edges with endpoint u in G . The Figure 1 in the next page, shows an example of an edge-graceful labeling of a graph. First, the graph involved, has five edges and five vertices. By following Definition 2.1 , the edges of the graph were labeled using distinct integers from 1 to 5, and the induced labels of the vertices are distinct integers from 0 to 4. Figure 1. An edge-graceful labeling of the cycle graph C_{5} Definition 2.2 . A fan graph denoted by F_{m,n} is defined as the graph join K_{m}+P_{n} , where K_{m} is the empty graph on m vertices and P_{n} is the path graph on n vertices. The case when m=1 corresponds to the usual fan graphs. Some examples of usual fan graphs are shown in Figure 2 below. Figure 2. Examples of usual fan graphs 2.2. Essential Number Theory Concepts For this subsection, we enumerate the important concepts in number theory that were utilized in this paper. For a more detailed discussion of basic concepts in number theory, readers may refer to Burton’s “Elementary Number Theory” [ 12 ] . Definition 2.3 . Let a and b be two positive integers, where a\leq b . We say that a divides b , written in symbols by a\mid b , if there is a positive integer c such that b=ac . Otherwise, we say that a does not divide b , denoted by a\nmid b . Now, if a\mid b , it also implies the following: (i) b is a multiple of a , (ii) a is a divisor of b , and (iii) a is a factor of b . Definition 2.4