EDGE ODD GRACEFUL GRAPHS
1:14 AM
INTRODUCTION
- Graph theory was born in 1736 with Euler’s paper in which he solved the Konigsberg bridge problem. For the next 100 years nothing more was done in the field. In 1847, G.R. Kirchhoff (1824-1887) developed the theory of trees for their applications in electrical networks.
- Ten years later,
Cayley (1821-1895) discovered trees while he was trying to enumerate the
isomers of saturated hydrocarbons
- At the time of Kirchhoff and Cayley, two other milestones in Graph theory were laid. One was the four color conjecture, which states that four colors are sufficient for coloring any atlas (a map on a plane) such that the countries with common boundaries have different colors.
- It is believed that A.F. Mobius (1790-1868) first presented the four colour problem in one of his lectures in 1840. About 10 years later, De Morgan (1806-1871) discussed this problem with his fellow mathematicians in London.
- De Morgan’s letter was the first authenticated reference to the four colour problem
- The structure of graphs admits a variety of functions that assign real number to their vertices and edges so that certain given conditions are satisfied.
- Numbered undirected graphs are becoming an increasingly useful family of mathematical models for a broad range of applications.
- Rosa [1967] introduced graph labeling, later on called as graceful labeling. The graceful labeling problem is to determine which graphs are graceful.
- Given a graph G consisting of vertices and edges, a vertex labeling of G is an assignment f of labels to the vertices of G that produces for each edge xy a label depending on the vertex labels f(x) and f(y).
- A complete summary of graceful, non-graceful graphs and the results along with some unproven conjectures can be found in Gallian’s Dynamic Survey [2010] of graph labeling.
- The survey reveals that the gracefulness of several classes of graphs has already been established. For example, all the paths Pn, all the trees, the complete graphs Kn for n < 5, all the wheels, etc., are graceful.
- The graceful labeling of graphs is perceived to be a primarily theoretical subject in the field of graph theory and Discrete Mathematics.
Graph
labeling:
- A graph labeling is an assignment of integers to the vertices or edges, or both, subject to certain conditions. Graph labeling were first introduced in the late 1960’s.
- Rosa [1967] defined a β-valuation of a graph G with e edges as an injection from the vertices of G to the set {0, 1, 2, …, e} such that when each edge xy is assigned the label │f(x) - f(y)│the resulting edge labels are distinct.
- β-valuations are functions that produce graceful labeling. However, the term graceful labeling was not used until Golomb [1977] studied such labeling later.
- Sheppard [1976] has shown that there are exactly q! gracefully labeled graphs with q edges. Rosa [1967] has identified essentially three reasons why a graph fails to be graceful:
- (1) G has “too many vertices” and “not enough edges,” (2) G “has too many edges,” and (3) G “has the wrong parity.” An infinite class of graphs that are not graceful for the second reason is given in [1986].
- As an example of the third condition, Rosa [1967] has shown that if every vertex has even degree and the number of edges is congruent to 1 or 2 (mod 4),
- then the graph is not graceful. In particular, the cycles C4n+1 and C4n+2 are not graceful.
- Acharya [1982] obtained that every graph can be embedded as an induced subgraph of a graceful graph and a connected graph can be embedded as an induced subgraph of a graceful connected graph.
- Acharya, Rao, and Arumugam [2008] found: every triangle - free graph can be embedded as an induced subgraph of a triangle - free graceful graph; every planar graph can be embedded as an induced subgraph of a planar graceful graph; and every tree can be embedded as an induced subgraph of a graceful tree. These results demonstrate that there is no forbidden subgraph characterization of these particular kinds of graceful graphs.
- The graceful labeling problem is to determine which graphs are graceful. When studying graceful labeling, we consider only finite graphs. For all notations in graph theory we follow Harary [2001].
- While the graceful labeling of graphs is perceived to be a primarily theoretical subject in the field of graph theory and discrete mathematics, gracefully labeled graphs often serve as models in a wide range of applications. Such applications include coding theory, X-ray crystallography, Radar, Astronomy, Circuit design, Communication network addressing, Data base management, and models for constraint programming over finite domains. Considering this point as a core, A. Solairaju and K. Chitra [2008] introduced a new concept of labeling called an Edge - Odd Graceful Labeling (EOGL).
- They defined that a labeling is said to be an EOGL if there exists a bijection f from E to {1, 3, ..., 2q-1} so that the induced mapping f+ from V to {0, 1, 2, …, 2q-1} given by f+(x) ≡ ∑{f(xy)/ xyÎE}( mod 2k), where the vertex x is incident with other vertex y and k = max{p, q} makes all the edges distinct and odd. A graph G with p vertices and q edges is said to be an edge - odd graceful graph if it admits EOGL.
- Chapter 1 covers some basic definitions which are needed for subsequent chapters.
- Chapter 2 is entitled as some results on “ Edge odd graceful graphs”. The definitions of graceful graphs and some theorems on edge odd graceful labeling of Pn +N7, Pn +N8, Pn +N9, Pn +N10 are obtained.
0 comments