Graph labeling

Last updated

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]

Contents

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. [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 α-, β-, and ρ-labelings. [5] β-labelings were later renamed as "graceful" by Solomon Golomb, and the name has been popular since.

Special cases

Graceful labeling

A graceful labeling; vertex labels are in black and edge labels in red Graceful labeling.svg
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". [6]

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. [7]

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. [8] The seven-page book graph K1,7 × K2 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 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}. [11]

Related Research Articles

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Extremal graph theory</span>

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Exact coloring</span>

In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. That is, it is a partition of the vertices of the graph into disjoint independent sets such that, for each pair of distinct independent sets in the partition, there is exactly one edge with endpoints in each set.

<span class="mw-page-title-main">Erdős–Faber–Lovász conjecture</span>

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

In graph theory, an edge-graceful labeling is a type of graph labeling for simple, connected graphs in which no two distinct edges connect the same two distinct vertices and no edge connects a vertex to itself.

<span class="mw-page-title-main">Circulant graph</span> Undirected graph acted on by a vertex-transitive cyclic group of symmetries

In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings.

A magic graph is a graph whose edges are labelled by the first q positive integers, where q is the number of edges, so that the sum over the edges incident with any vertex is the same, independent of the choice of vertex; or it is a graph that has such a labelling. The name "magic" sometimes means that the integers are any positive integers; then the graph and the labelling using the first q positive integers are called supermagic.

<span class="mw-page-title-main">Paley graph</span>

In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yield an infinite family of symmetric conference matrices. Paley graphs allow graph-theoretic tools to be applied to the number theory of quadratic residues, and have interesting properties that make them useful in graph theory more generally.

<span class="mw-page-title-main">Graceful labeling</span> Type of graph vertex labeling

In graph theory, a graceful labeling of a graph with m edges is a labeling of its vertices with some subset of the integers from 0 to m inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and m inclusive. A graph which admits a graceful labeling is called a graceful graph.

<span class="mw-page-title-main">Friendship graph</span> Graph of triangles with a shared vertex

In the mathematical field of graph theory, the friendship graphFn is a planar, undirected graph with 2n + 1 vertices and 3n edges.

<span class="mw-page-title-main">Windmill graph</span> Graph family made by joining complete graphs at a universal node

In the mathematical field of graph theory, the windmill graphWd(k,n) is an undirected graph constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kk at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.

Anton Kotzig was a Slovak–Canadian mathematician, expert in statistics, combinatorics and graph theory.

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal, who first posed it as an open problem in a paper from 1977.

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.

References

  1. 1 2 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-2023". The Electronic Journal of Combinatorics. doi: 10.37236/27 .
  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. 53. Institute of Combinatorics and its Applications: 31–46. ISSN   1183-1278. S2CID   16184248.
  7. ↑ Lo, Sheng-Ping (1985). "On edge-graceful labelings of graphs". Congressus Numerantium. Sundance Conference, Utah. Vol. 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 is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.