To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Graph labeling

From Wikipedia, the free encyclopedia

In the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.[1]

Formally, given a graph , a vertex labelling is a function of to a set of labels; a graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labelling is a function of 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 , where 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 labelling 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 labellings trace their origins to labellings presented by Alexander Rosa in his 1967 paper.[4] Rosa identified three types of labellings, which he called α, β-, and ρ-labellings.[5] β-labellings were later renamed as "graceful" by Solomon Golomb, and the name has been popular since.

Special cases

Graceful labelling

A graceful labelling; vertex labels are in black and edge labels in red
A graceful labelling; vertex labels are in black and edge labels in red

A graph is known as graceful when its vertices are labeled from 0 to |E|, the size of the graph, and this labelling induces an edge labelling from 1 to |E|. For any edge e, the label of e is the positive difference between the two vertices incident with e. In other words, if e is incident with vertices labeled i and j, e will be labeled |ij|. Thus, a graph G = (V, E) is graceful if and only if there exists an injection that induces a bijection from E to the positive integers up to |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 labelling 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 labelling

An edge-graceful labelling on a simple graph without loops or multiple edges on p vertices and q edges is a labelling of the edges by distinct integers in {1, …, q} such that the labelling on the vertices induced by labelling 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 labelling.

Edge-graceful labellings were first introduced by Sheng-Ping Lo in 1985.[7]

A necessary condition for a graph to be edge-graceful is "Lo's condition":

Harmonious labelling

A "harmonious labelling" 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 labelling. 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 K1,7 × K2 provides an example of a graph that is not harmonious.[9]

Graph colouring

A graph colouring is a subclass of graph labellings. Vertex colourings assign different labels to adjacent vertices, while edge colourings assign different labels to adjacent edges.[10]

Lucky labelling

A lucky labelling 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 neighbours 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 labelling with the integers .[11]

References

  1. ^ a b Weisstein, Eric W. "Labeled graph". MathWorld.
  2. ^ Robert Calderbank, Different Aspects of Coding Theory, (1995) ISBN 0-8218-0379-4, p. 53"
  3. ^ "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
  4. ^ Gallian, J. "A Dynamic Survey of Graph Labellings, 1996-2005". The Electronic Journal of Combinatorics. Cite journal requires |journal= (help)
  5. ^ 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.
  6. ^ Vietri, Andrea (2008). "Sailing towards, and then against,the Graceful Tree Conjecture: some promiscuous results". Bulletin of the Institute of Combinatorics and Its Applications. Institute of Combinatorics and its Applications. 53: 31–46. ISSN 1183-1278. S2CID 16184248.
  7. ^ Lo, Sheng-Ping (1985). "On edge-graceful labelings of graphs". Congressus Numerantium. Sundance Conference, Utah. 50. pp. 231–241. Zbl 0597.05054.
  8. ^ 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.
  9. ^ Gallian, Joseph A. (1998). "A dynamic survey of graph labelling". Electronic Journal of Combinatorics. 5: Dynamic Survey 6. MR 1668059..
  10. ^ Chartrand, Gary; Egan, Cooroo; Zhang, Ping (2019). How to Label a Graph. SpringerBriefs in Mathematics. Springer. pp. 3–4. ISBN 9783030168636.
  11. ^ 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.
This page was last edited on 5 August 2021, at 16:13
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.