Home | Blog | Wiki | About

Some terms used in graph theory.

(Thanks to Ganesh sir for introducing and/or reminding me about a lot of this.)

---

Graph

• Consists of 2 sets:
  • set of nodes/vertices
  • set of edges

Tour

• A closed trail.
• A path consisting of all vertices in the graph.
• ie, a walk with no repeating

Euler cycle

• Cycle where no edges are repeated.
• aka Eulerian circuit
• aka Eulerian trail

Hamiltonian cycle

• Cycle where no edges are repeated.

Mixed graph

Graph containing a mix of directed and undirected edges.

Hypergraph

A graph with hyperedges. ie, an edge which is connects more than just two vertices.

Undirected graph

Simple graph

Graph satisfying the following conditions:

• no loops (edge incident only on one vertex).
• no more than one edge between the same pair of vertices.

Multi graph

A non-simple graph.

ie, has a loop or parallel edges.

Adjacent vertices

Vertices linked by an edge.

Walk

• An alternating sequence of vertices and edges, which joins a sequence of vertices.
• aka chain
• open walk :: starting and ending vertices are different
• closed walk :: same starting and ending vertex

Trail

A walk with distinct edges.

Path

A walk with distinct vertices.

Cycle

• A closed walk with distinct vertices.
• aka circuit??

Connected graph

All vertices linked together by edges. "All vertex pairs are joined by a path". There exists a path between every pair of nodes.

Need not be a complete graph.

Induced subgraph

A type subgraphs.

Line graph

Acyclic graph (Forest)

Graph without any cycles.

Tree

Just a connected acyclic graph.

Rooted tree

Tree with a distinguished root vertex.

Nodes

Vertices of a tree.

Leaves

Nodes of a tree when they are adjacent to only one vertex and are not root.

Directed graphs

Head and tail of an edge

Head

Vertex from which the edge starts.

Tail

Vertex at which the edge ends.

Successor and predecessor vertices in a DAG

If there is a path from a vertex A to another vertex B,

• B is a successor of A
• A is a predecessor of B
• B is reachable from A

Direct successor/predecessor means the vertices are directly connected. ie, there vertices are directly linked by a single edge. The vertices are then said to be adjacent.

Indegree of a vertex

Number of edges for which the vertex is the head.

Outdegree of a vertex

Number of edges for which the vertex is the tail.

Walk

An alternating sequence of vertices and edges with the same direction.

Directed acyclic graph (DAG)

Represents a partial ordering.

Polar DAG

A DAG with two distinguished vertices: a source and a sink.

Source

All vertices are reachable from the source vertex of the graph.

Sink

Sink vertex is reachable from all vertices of the graph.

Incidence matrix

Rows = vertices Columns = edges

Adjacency matrix

Rows = vertices Columns = vertices

Perfect graphs

Clique of a graph

A complete subgraph.

Maximum clique of a graph

Largest possible clique of a graph.

Clique number of a graph

Cardinality (ie, number of vertices) of the maximum clique of the graph.

Orientation

Orientation of an undirected graph is an assignment of exactly one direction to all edges of that graph.

Graphs with names

• Steiner tree

Petersen graph

• Undirected
• 10 nodes

Planar graph

Graph that can be drawn in 2D with no two edges crossing each other.

Examples:

• Petersen graph
• k4
• graph representation of a 3D cube

k4 (complete graph with 4 nodes) is planar (biggest planar complete graph??).

               +---------+
N----N         |         |
|\  /|         N----N    |
| \/ |         |   /|    |
| /\ |    ≡    |  / |    |
|/  \|         | /  |    |
N----N         |/   |    |
               N----N----+

A cube can be made into a planar graph.

N-----------N
|\         /|
| \       / |
|  N-----N  |
|  |     |  |
|  |     |  |
|  N-----N  |
| /       \ |
|/         \|
N-----------N

Euler's formula for planar graphs

l3

|F| - |E| + |V| = 2

Minor of a graph

Graph that can be formed by deleting some edges, vertices and 'merging' some vertices if needed.

For example²:

    B       
    |       
D---Z---E   
    |       
    C       

is a minor of

    B
   /|
  / |
 /  |
D---X---Y---E---F
        |  /
        | /
        |/
        C

formed by

• deleting X-Y edge, and merging X and Y (ie, contracting the vertices X and Y)
• deleting node F
• deleting CE, BD

Diameter of a graph

Length of largest possible path within graph.

General

• Wagner's theorem: A finite graph is planar only if it doesn't have k5 or k3,3 as one of

its minors.

Interesting bits

• An octahedron can be made into a planar graph.

More

• Topological sort
• Bipartite graph
  • Every edge will one end point in A and other in B
• Split graph
• Chordal graph
  • Every induced cycle is a triangle.
• Independent set
• Spanning tree
• Mixed multi-graph
• Radius and diameter of a digraph??
• Eccentricity of a graph
• oriented diameter
• 2 edge connected graph: remove an edge and the graph is still connected
• Strongly connected: path between any pair of vertices
• 'Bridge' in a graph: remove a bridge in a connected graph and the graph becomes disconnected.

References

• Introduction to algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• Synthesis and optimization of digital circuits - Giovanni De Micheli
• https://en.wikipedia.org/wiki/Glossary_of_graph_theory