Английская Википедия:Graph labeling
Шаблон:Short description Шаблон:Use American English
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.[1]
Formally, given a graph Шаблон:Math, a vertex labeling is a function of Шаблон:Mvar 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 Шаблон:Mvar 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 Шаблон:Math, where Шаблон:Math is the number of vertices in the graph.[1] 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.[2]
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.[3]
History
Most graph labelings trace their origins to labelings presented by Alexander Rosa in his 1967 paper.[4] Rosa identified three types of labelings, which he called Шаблон:Math-, Шаблон:Math-, and Шаблон:Math-labelings.[5] Шаблон:Math-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 when its vertices are labeled from 0 to Шаблон:Math, the size of the graph, and this labeling induces an edge labeling from 1 to Шаблон:Math. For any edge Шаблон:Mvar, the label of Шаблон:Mvar is the positive difference between the two vertices incident with Шаблон:Mvar. In other words, if Шаблон:Mvar is incident with vertices labeled Шаблон:Mvar and Шаблон:Mvar, Шаблон:Mvar will be labeled Шаблон:Math. Thus, a graph Шаблон:Math is graceful if and only if there exists an injection that induces a bijection from Шаблон:Mvar to the positive integers up to Шаблон:Math.
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".[6]
Edge-graceful labeling
Шаблон:Main An edge-graceful labeling on a simple graph without loops or multiple edges on Шаблон:Mvar vertices and Шаблон:Mvar edges is a labeling of the edges by distinct integers in Шаблон:Math such that the labeling on the vertices induced by labeling a vertex with the sum of the incident edges taken modulo Шаблон:Mvar assigns all values from 0 to Шаблон:Math to the vertices. A graph Шаблон:Math 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.[7]
A necessary condition for a graph to be edge-graceful is "Lo's condition":
- <math>q(q + 1) = \frac{p(p - 1)}{2} \mod p.</math>
Harmonious labeling
A "harmonious labeling" on a graph Шаблон:Mvar is an injection from the vertices of Шаблон:Mvar to the group of integers modulo Шаблон:Mvar, where Шаблон:Mvar is the number of edges of Шаблон:Mvar, that induces a bijection between the edges of Шаблон:Mvar and the numbers modulo Шаблон:Mvar by taking the edge label for an edge Шаблон:Math to be the sum of the labels of the two vertices Шаблон:Math. 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.[8] The seven-page book graph Шаблон:Math provides an example of a graph that is not harmonious.[9]
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.[10]
Lucky labeling
A lucky labeling of a graph Шаблон:Mvar is an assignment of positive integers to the vertices of Шаблон:Mvar such that if Шаблон:Math denotes the sum of the labels on the neighbors of Шаблон:Mvar, then Шаблон:Mvar is a vertex coloring of Шаблон:Mvar. The "lucky number" of Шаблон:Mvar is the least Шаблон:Mvar such that Шаблон:Mvar has a lucky labeling with the integers Шаблон:Math[11]
References
- ↑ 1,0 1,1 Шаблон:Mathworld
- ↑ Robert Calderbank, Different Aspects of Coding Theory, (1995) Шаблон:ISBN, p. 53"
- ↑ "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, Шаблон:ISBN, p. 313
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite conference
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite conference
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal.
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
