Some definitions in Graph Theory

[English | Français]

Basic terminology


  •  A graph is a pair of sets (V, E) where V is the vertex-set and E the edge-set is a family of pairs (possibly directed) of V.

  •  The subgraph of G induced by a subset W of its vertex-set V is the graph formed by the vertices in W and all edges whose two endpoints are in W.

  •  A graph is called complete when every pair of vertices is an edge.

  •  A clique of G is a subset of vertices in which every pair is an edge.

  •  A stable set of G is a subset of vertices with no edge between any two of them.

  •  The degree of a vertex of G is the number of edges incident to it.

  •  A graph is connected when there exists a path between any two vertices.

    •  
  •  A hypergraph is a pair of sets (V,F) where V is the vertex-set and F is a family of non empty subsets of V (called also edges or hyperedges). See for example the Berge's book on hypergraphs, or the chapter written by Pierre Duchet in the collective book Handbook of Combinatorics.

    •  

    Domination problems


  •  In a graph (resp. a directed graph) G a dominating set is a set of vertices A such that every vertex outside A has at least one neighbour (resp. one successor) in A. The dominating number of G, denoted gamma(G), is the size of a smallest dominating set of G. Computing gamma(G) is an NP-hard problem, even when G is bipartite.

  •   In a directed graph a kernel is a set both stable and dominating. Deciding if a graph has a kernel is an NP-complete problem.

    For more details see the chapter on kernels in Berge's book on graphs.


    • Coloring, Perfect Graphs


  •  In a graph (or even a hypergraph) G = (V, E) a k-coloring is an assignment of colours from {1, ..., k} to the vertices (one per vertex) such that, for every edge uv of G, the vertices u and v have different colours (for a hypergraph we require that each edge carry at least two different colours). A graph is called k-colorable if it has a k-coloring. Deciding if a graph is k-colorable for any given k (at least 3) is an NP-complete problem [REF: Garey & Johnson]. A lot of problems on coloring are presented in the recent book by Jensen and Toft.

    On the subject of coloring, one may visit with interest Joseph Culberson's page at Alberta University (Canada).

  •  The chromatic number of G, denoted Chi(G), is the smallest k such that G is k-colorable.

  •  A graph G is perfect if, for any induced subgraph H of G, the chromatic number of H is equal to the size of a maximum clique of H, that is, Chi(H)=omega(H). The theory of perfect graphs is very rich; see Golumbic or Berge & Chvátal.


    •  

    Flow


  •  In a directed graph G, a flow is the assignment of a real value f(e) to each arc e of G such that, for each vertex, the sum of entering flows is equal to the sum of leaving flows (Kirchhoff's law). Usually a capacity c(e) is given on each arc, imposing an upper bound on the flow allowed on this arc; the maximum flow problem is then to find a flow whose value on a specified returning arc (sink to source) is maximum. Moreover, some transportation cost per unit may be given on each arc, and the problem is then to find a (maximum) flow with minimum cost. These problems have efficient polynomial-time solutions and numerous applications or generalizations, see for instance the recent book by Ahuja, Magnanti, Orlin.


     

    Connectivity


  •  A graph G is k-vertex-connected (resp. k-edge-connected) if we need to delete at least k vertices (resp. k edges) in order to get a non-connected graph. The (vertex or edge)-connectivity of the graph is the largest k such that G is k-connected. These two parameters may be computed by particular flows algorithms.

    Recently, some new results (Karger; Nagamochi et Ibaraki; Frank) have made it possible to compute the edge-connectivity of a graph without using flow techniques.

     

    Products of graphs


  •  The square product of G and H, is the graph whose vertex-set is the cartesian product of V(G) and V(H), and where the pair (ax, by) is an edge if and only if either a=b and xy is an edge of H, or x=y and ab is an edge of G.

    The square product of two paths is frequently called the grid graph.

  •  The cross product of G and H, is the graph whose vertex-set is the cartesian product of V(G) and V(H), and the pair (ax, by) is an edge if and only if ab is an edge of G and xy is an edge of H.

    The cross product of two paths has two connected components, which are isomorphic to subgraphs of a grid.


    •  

    Hamiltonicity


  •  A Hamiltonian cycle of a graph G is an elementary cycle going through all vertices of G. A graph is Hamiltonian if it has a Hamiltonian cycle. Deciding if a graph is Hamiltonian is an NP-complete problem. See the article by Gould for a recent survey on Hamiltonicity.

  •  The Traveling Salesman Problem is to find a Hamiltonian cycle of a Hamiltonian graph (where every edge has a length) with minimum total length. This is an important problem in Operations Research. See the book by Lawler, Lenstra, Rinnooy Kan & Schmoys.

    •  

    Eulerian problems


  •  An Eulerian walk in a graph is a walk going exactly once through each edge. A graph is called Eulerian if such a closed walk exists; this is equivalent to the graph being connected and with even degrees for all vertices (this is a theorem of Euler, frequently considered the first theorem in Graph Theory). The book by Fleischner deals with numerous questions and generalizations on this subject.

  • The city of Königsberg (now Kaliningrad) had seven bridges on the Pregel River. People were wondering whether it would be possible to take a walk through the city passing exactly once on each bridge. Euler built the representative graph, observed that it had vertices of odd degree, and proved that this made such a walk impossible.

  •  The so-called Chinese Postman Problem (named after the Chinese mathematician Mei Go Guan) consists in finding a closed walk going through every edge at least once, in a graph that is not necessarily Eulerian, with a minimum total length. See Lovász & Plummer, or Ahuja, Magnanti & Orlin.

    •  

    Planarity


  •  One says that a graph is planar if it can be represented on a plane drawing in such a way that the edges are lines that do not cross each other. Kuratowski gave in 1933 a characterization of planar graphs by forbidden "minors". There exist several polynomial-time algorithms to determine if a graph is planar, and, when it is, to find a planar representation. See for example the recent book by Nishizeki and Chiba.

  •  A geographic map can be modelized by a planar graph whose vertices are the regions and whose edges are the pairs of neighbouring regions. One may want to color the regions in such a way that any two neighbouring regions have different colours. It was known to cartographers for a long time that this can be achieved with only four colours. However, despite many failed attempts, the first mathematical proof of this four colour problem appeared only in 1976, by Appel and Haken, and it uses a computer to check many cases. A new proof, more compact, but in the same spirit, was given by Robertson, Seymour, Thomas and Sanders.

     

    Matching


  •  A matching is a set of pairwise non-adjacent edges. One can find in polynomial time a matching of maximum size (or even weight). Based on the pioneering works by König, Hall, Tutte, Edmonds, Gallai, Lovász, matching theory is very rich; see for example the book by Lovász & Plummer.


    •  

    Some combinatorial invariants


  •  The size of a largest clique of G is denoted omega(G).

  •  The size of a largest stable set of G is denoted alpha(G).