In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.
Formally, given a graph G = (V, E), a vertex labeling is a function of V to a set of labels; a graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labeling is a function of E to a set of labels. In this case, the graph is called an edge-labeled graph.
When the edge labels are members of an ordered set (e.g., the real numbers), it may be called a weighted graph.
When used without qualification, the term labeled graph generally refers to a vertex-labeled graph with all labels distinct. Such a graph may equivalently be labeled by the consecutive integers { 1, …, |V| } , where |V| is the number of vertices in the graph. For many applications, the edges or vertices are given labels that are meaningful in the associated domain. For example, the edges may be assigned weights representing the "cost" of traversing between the incident vertices.
In the above definition a graph is understood to be a finite undirected simple graph. However, the notion of labeling may be applied to all extensions and generalizations of graphs. For example, in automata theory and formal language theory it is convenient to consider labeled multigraphs, i.e., a pair of vertices may be connected by several labeled edges.
History
Most graph labelings trace their origins to labelings presented by Alexander Rosa in his 1967 paper. Rosa identified three types of labelings, which he called α-, β-, and ρ-labelings.β-labelings were later renamed as "graceful" by Solomon Golomb, and the name has been popular since.
Special cases
Graceful labeling
A graph is known as graceful if its vertices are labeled from 0 to |E|, the size of the graph, and if this vertex labeling induces an edge labeling from 1 to |E|. For any edge e, the label of e is the positive difference between the labels of the two vertices incident with e. In other words, if e is incident with vertices labeled i and j, then e will be labeled |i − j|. Thus, a graph G = (V, E) is graceful if and only if there exists an injection from V to {0, ..., |E|} that induces a bijection from E to {1, ..., |E|}.
In his original paper, Rosa proved that all Eulerian graphs with size equivalent to 1 or 2 (mod 4) are not graceful. Whether or not certain families of graphs are graceful is an area of graph theory under extensive study. Arguably, the largest unproven conjecture in graph labeling is the Ringel–Kotzig conjecture, which hypothesizes that all trees are graceful. This has been proven for all paths, caterpillars, and many other infinite families of trees. Anton Kotzig himself has called the effort to prove the conjecture a "disease".
Edge-graceful labeling
An edge-graceful labeling on a simple graph without loops or multiple edges on p vertices and q edges is a labeling of the edges by distinct integers in {1, …, q} such that the labeling on the vertices induced by labeling a vertex with the sum of the incident edges taken modulo p assigns all values from 0 to p − 1 to the vertices. A graph G is said to be "edge-graceful" if it admits an edge-graceful labeling.
Edge-graceful labelings were first introduced by Sheng-Ping Lo in 1985.
A necessary condition for a graph to be edge-graceful is "Lo's condition":
Harmonious labeling
A "harmonious labeling" on a graph G is an injection from the vertices of G to the group of integers modulo k, where k is the number of edges of G, that induces a bijection between the edges of G and the numbers modulo k by taking the edge label for an edge (x, y) to be the sum of the labels of the two vertices x, y (mod k). A "harmonious graph" is one that has a harmonious labeling. Odd cycles are harmonious, as are Petersen graphs. It is conjectured that trees are all harmonious if one vertex label is allowed to be reused. The seven-page book graph K1,7 × K2 provides an example of a graph that is not harmonious.
Graph coloring
A graph coloring is a subclass of graph labelings. Vertex colorings assign different labels to adjacent vertices, while edge colorings assign different labels to adjacent edges.
Lucky labeling
A lucky labeling of a graph G is an assignment of positive integers to the vertices of G such that if S(v) denotes the sum of the labels on the neighbors of v, then S is a vertex coloring of G. The "lucky number" of G is the least k such that G has a lucky labeling with the integers {1, …, k}.
References
- Weisstein, Eric W. "Labeled graph". MathWorld.
- Robert Calderbank, Different Aspects of Coding Theory, (1995) ISBN 0-8218-0379-4, p. 53"
- "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
- Gallian, J. "A Dynamic Survey of Graph Labellings, 1996-2023". The Electronic Journal of Combinatorics. doi:10.37236/27.
- Rosa, Alexander (1967). On certain valuations of the vertices of a graph. Theory of Graphs, Int. Symp. Rome July 1966. Gordon and Breach. pp. 349–355. Zbl 0193.53204.
- Vietri, Andrea (2008). "Sailing towards, and then against, the Graceful Tree Conjecture: some promiscuous results". Bulletin of the Institute of Combinatorics and its Applications. 53. Institute of Combinatorics and its Applications: 31–46. ISSN 1183-1278. S2CID 16184248.
- Lo, Sheng-Ping (1985). "On edge-graceful labelings of graphs". Congressus Numerantium. Sundance Conference, Utah. Vol. 50. pp. 231–241. Zbl 0597.05054.
- Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. Problem C13, pp. 190–191. ISBN 0-387-20860-7. Zbl 1058.11001.
- Gallian, Joseph A. (1998). "A dynamic survey of graph labelling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059..
- Chartrand, Gary; Egan, Cooroo; Zhang, Ping (2019). How to Label a Graph. SpringerBriefs in Mathematics. Springer. pp. 3–4. ISBN 9783030168636.
- Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor (2009). "Lucky labellings of graphs". Inf. Process. Lett. 109 (18): 1078–1081. doi:10.1016/j.ipl.2009.05.011. Zbl 1197.05125.
In the mathematical discipline of graph theory a graph labeling is the assignment of labels traditionally represented by integers to edges and or vertices of a graph Formally given a graph G V E a vertex labeling is a function of V to a set of labels a graph with such a function defined is called a vertex labeled graph Likewise an edge labeling is a function of E to a set of labels In this case the graph is called an edge labeled graph When the edge labels are members of an ordered set e g the real numbers it may be called a weighted graph When used without qualification the term labeled graph generally refers to a vertex labeled graph with all labels distinct Such a graph may equivalently be labeled by the consecutive integers 1 V where V is the number of vertices in the graph For many applications the edges or vertices are given labels that are meaningful in the associated domain For example the edges may be assigned weights representing the cost of traversing between the incident vertices In the above definition a graph is understood to be a finite undirected simple graph However the notion of labeling may be applied to all extensions and generalizations of graphs For example in automata theory and formal language theory it is convenient to consider labeled multigraphs i e a pair of vertices may be connected by several labeled edges HistoryMost graph labelings trace their origins to labelings presented by Alexander Rosa in his 1967 paper Rosa identified three types of labelings which he called a b and r labelings b labelings were later renamed as graceful by Solomon Golomb and the name has been popular since Special casesGraceful labeling A graceful labeling vertex labels are in black and edge labels in red A graph is known as graceful if its vertices are labeled from 0 to E the size of the graph and if this vertex labeling induces an edge labeling from 1 to E For any edge e the label of e is the positive difference between the labels of the two vertices incident with e In other words if e is incident with vertices labeled i and j then e will be labeled i j Thus a graph G V E is graceful if and only if there exists an injection from V to 0 E that induces a bijection from E to 1 E In his original paper Rosa proved that all Eulerian graphs with size equivalent to 1 or 2 mod 4 are not graceful Whether or not certain families of graphs are graceful is an area of graph theory under extensive study Arguably the largest unproven conjecture in graph labeling is the Ringel Kotzig conjecture which hypothesizes that all trees are graceful This has been proven for all paths caterpillars and many other infinite families of trees Anton Kotzig himself has called the effort to prove the conjecture a disease Edge graceful labeling An edge graceful labeling on a simple graph without loops or multiple edges on p vertices and q edges is a labeling of the edges by distinct integers in 1 q such that the labeling on the vertices induced by labeling a vertex with the sum of the incident edges taken modulo p assigns all values from 0 to p 1 to the vertices A graph G is said to be edge graceful if it admits an edge graceful labeling Edge graceful labelings were first introduced by Sheng Ping Lo in 1985 A necessary condition for a graph to be edge graceful is Lo s condition q q 1 p p 1 2modp displaystyle q q 1 frac p p 1 2 mod p Harmonious labeling A harmonious labeling on a graph G is an injection from the vertices of G to the group of integers modulo k where k is the number of edges of G that induces a bijection between the edges of G and the numbers modulo k by taking the edge label for an edge x y to be the sum of the labels of the two vertices x y mod k A harmonious graph is one that has a harmonious labeling Odd cycles are harmonious as are Petersen graphs It is conjectured that trees are all harmonious if one vertex label is allowed to be reused The seven page book graph K1 7 K2 provides an example of a graph that is not harmonious Graph coloring A graph coloring is a subclass of graph labelings Vertex colorings assign different labels to adjacent vertices while edge colorings assign different labels to adjacent edges Lucky labeling A lucky labeling of a graph G is an assignment of positive integers to the vertices of G such that if S v denotes the sum of the labels on the neighbors of v then S is a vertex coloring of G The lucky number of G is the least k such that G has a lucky labeling with the integers 1 k ReferencesWeisstein Eric W Labeled graph MathWorld Robert Calderbank Different Aspects of Coding Theory 1995 ISBN 0 8218 0379 4 p 53 Developments in Language Theory Proc 9th Internat Conf 2005 ISBN 3 540 26546 5 p 313 Gallian J A Dynamic Survey of Graph Labellings 1996 2023 The Electronic Journal of Combinatorics doi 10 37236 27 Rosa Alexander 1967 On certain valuations of the vertices of a graph Theory of Graphs Int Symp Rome July 1966 Gordon and Breach pp 349 355 Zbl 0193 53204 Vietri Andrea 2008 Sailing towards and then against the Graceful Tree Conjecture some promiscuous results Bulletin of the Institute of Combinatorics and its Applications 53 Institute of Combinatorics and its Applications 31 46 ISSN 1183 1278 S2CID 16184248 Lo Sheng Ping 1985 On edge graceful labelings of graphs Congressus Numerantium Sundance Conference Utah Vol 50 pp 231 241 Zbl 0597 05054 Guy Richard K 2004 Unsolved problems in number theory 3rd ed Springer Verlag Problem C13 pp 190 191 ISBN 0 387 20860 7 Zbl 1058 11001 Gallian Joseph A 1998 A dynamic survey of graph labelling Electronic Journal of Combinatorics 5 Dynamic Survey 6 MR 1668059 Chartrand Gary Egan Cooroo Zhang Ping 2019 How to Label a Graph SpringerBriefs in Mathematics Springer pp 3 4 ISBN 9783030168636 Czerwinski Sebastian Grytczuk Jaroslaw Ẓelazny Wiktor 2009 Lucky labellings of graphs Inf Process Lett 109 18 1078 1081 doi 10 1016 j ipl 2009 05 011 Zbl 1197 05125
