**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Graph labeling

Summary

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.
Formally, given a graph G = (V, E), a vertex labelling 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 labelling 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, ..., } , where 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 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.
Most graph labellings trace their origins to labellings presented by Alexander Rosa in his 1967 paper. Rosa identified three types of labellings, which he called α-, β-, and ρ-labellings. β-labellings were later renamed as "graceful" by Solomon Golomb, and the name has been popular since.
Graceful labeling
A graph is known as graceful when its vertices are labeled from 0 to , the size of the graph, and this labelling induces an edge labelling from 1 to . 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 .

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (2)

Related lectures (27)

Markov Chains and Algorithm Applications

Covers the application of Markov chains and algorithms for function optimization and graph colorings.

Information Theory: Basics

Covers the basics of information theory, entropy, and fixed points in graph colorings and the Ising model.

Statistical Analysis of Network Data: Noisy Sampled Networks

Explores statistical analysis of network data, covering noisy sampled networks, likelihood estimation, multilayer networks, and directed networks.

Related concepts (7)

A first course in statistical network analysis and applications.

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun

Graph labeling

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. Formally, given a graph G = (V, E), a vertex labelling 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 labelling 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.

Cartesian product of graphs

In graph theory, the Cartesian product G □ H of graphs G and H is a graph such that: the vertex set of G □ H is the Cartesian product V(G) × V(H); and two vertices (u,u' ) and (v,v' ) are adjacent in G □ H if and only if either u = v and u' is adjacent to v' in H, or u' = v' and u is adjacent to v in G. The Cartesian product of graphs is sometimes called the box product of graphs [Harary 1969]. The operation is associative, as the graphs (F □ G) □ H and F □ (G □ H) are naturally isomorphic.

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.