Graph Theory Resources

 

This page provides some Graph Theory (GT) resources.

Good website about intro to GT.

GT – Basics

 

G properties

  •      A disconnected graph has infinite diameter (West 2000, p. 71).
      • A topological space decomposes into its connected components. The connectedness relation between two pairs of points satisfies transitivity, i.e., if a∼b and b∼c then a∼c. Hence, being in the same component is an equivalence relation, and the equivalence classes are the connected components.Using pathwise-connectedness, the pathwise-connected component containing x in X is the set of all y pathwise-connected to x. That is, it is the set of y such that there is a continuous path from x to y.Technically speaking, in some topological spaces, pathwise-connected is not the same as connected. A subset Y of X is connected if there is no way to write Y=U union V with U and V disjoint open sets. Every topological space decomposes into a disjoint union X= union Y_i where the Y_i are connected. The Y_i are called the connected components of X.The connected components of a graph G are the set of largest subgraphs of G that are each connected.
      • An edge in an undirected connected graph is a bridge iff removing it disconnects the graph.For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of disconnected components.

      •  Graph Bridge
    • A bridge of a connected graph is a graph edge whose removal disconnects the graph (Chartrand 1985, p. 45; Skiena 1990, p. 177). More generally, a bridge is an edge of a not-necessarily-connected graph G whose removal increases the number of components of G (Harary 1994, p. 26). An edge of a connected graph is a bridge iff it does not lie on any cycle.A bridge is also known as an isthmus, cut-edge, or cut arc.Every edge of a tree is a bridge. A connected cubic graph contains a bridge iff it contains an articulation vertex (Skiena 1990, p. 177), i.e., if it is not a biconnected graph.A graph containing one or more bridges is said to be a bridged graph, while a graph containing no bridges is called a bridgeless graph.

      • The center of a graph G is the set of vertices of graph eccentricity equal to the graph radius (i.e., the set of central points). In the illustration below, center nodes are shown in red.
      • The radius of a graph is the minimum eccentricity among all vertices in the graph, and a center
        of a graph is a vertex with eccentricity equal to the radius. For a general graph, there may be several
        centers and a center is not necessarily on a diameter.

      • The periphery of a graph G is the subgraph of G induced by vertices that have graph eccentricities equal to the graph diameter.
      • for example, for the following graph, its periphery is: [0, 1, 2, 9] 
        radius: 4
diameter: 7
eccentricity: {0: 7, 1: 7, 2: 7, 3: 6, 4: 5, 5: 4, 6: 4, 7: 5, 8: 6, 9: 7}
center: [5, 6]

      • The distance d(u,v) between two vertices u and v of a finite graph is the minimum length of the paths connecting them (i.e., the length of a graph geodesic). If no such path exists (i.e., if the vertices lie in different connected components), then the distance is set equal to infty. In a grid graph the distance between two vertices is the sum of the “vertical” and the “horizontal” distances (right figure below).The matrix (d_(ij)) consisting of all distances from vertex v_i to vertex v_j is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.

        • TBA
  • GT Basic Properties at tutorialspoint.com
  • The concept of “strongly connected” and “weakly connected” graphs are defined for directed graphs.

A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs (i.e., for every pair of distinct vertices u and v there exists a directed path from u to v).

A digraph is weakly connected if when considering it as an undirected graph it is connected (i.e., for every pair of distinct vertices u and v there exists an undirected path (potentially running opposite the direction on an edge) from u to v).

In both cases, it requires that the undirected graph be connected, however strongly connected requires a stronger condition.  If a digraph is strongly connected, it is also weakly connected.

For example, the following graph is not a directed graph and so ought not get the label of “strongly” or “weakly” connected, but it is an example of a connected graph. As soon as you make your example into a directed graph, however, regardless of orientation on the edges, it will be weakly connected (and possibly strongly connected based on choices made).

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and depends on the context.

where E is the number of edges and V is the number of vertices in the graph. The maximum number of edges for an undirected graph is  |V|(|V|-1)/2, so the maximal density is 1 (for complete graphs) and the minimal density is 0 (Coleman & Moré 1983).

The density is 0 for a graph without edges and 1 for a complete graph. The density of multigraphs can be higher than 1.

Self loops are counted in the total number of edges so graphs with self loops can have density higher than 1.

Coleman, Thomas F.; Moré, Jorge J. (1983), “Estimation of sparse Jacobian matrices and graph coloring Problems”, SIAM Journal on Numerical Analysis, 20 (1): 187–209, doi:10.1137/0720013.

 

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

The adjacency matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position (v_i,v_j) according to whether v_i and v_j are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.

The illustration below  shows adjacency matrices for particular labelings of the claw graph, cycle graph C_4, and complete graph K_4.

Since the labels of a graph may be permuted without changing the underlying graph being represented, there are in general multiple possible adjacency matrices for a given graph.

The eigenvalues of a graph are defined as the eigenvalues of its adjacency matrix. The set of eigenvalues of a graph is called a graph spectrum.

The largest eigenvalue absolute value in a graph is called the spectral radius of the graph, and the second smallest eigenvalue of the Laplacian matrix of a graph is called its algebraic connectivity.

The numerically second smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of a graph G is known as the algebraic connectivity of the graph. This eigenvalue is greater than 0 iff G is a connected graph.

The spectral radius of a finite graph is defined as the largest absolute value of its graph spectrum, i.e., the largest absolute value of the graph eigenvalues (eigenvalues of the adjacency matrix).

The set of graph eigenvalues of the adjacency matrix is called the spectrum of the graph. (But note that in physics, the eigenvalues of the Laplacian matrix of a graph are sometimes known as the graph’s spectrum.) The spectrum of a graph G with n_i-fold degenerate

http://mathworld.wolfram.com/topics/GraphTheory.html

The vertex connectivity kappa(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Vertex connectivity is sometimes called “point connectivity” or simply “connectivity.”

A graph with kappa>0 is said to be connected, a graph with kappa>1 is said to be biconnected (Skiena 1990, p. 177), and in general, a graph with vertex connectivity k is said to be k-connected.

A block is a maximal biconnected subgraph of a given graph G. In the illustration below, the blocks are {2,5,6}, {3,4,6,7}, and {1,7}.

If a graph G is biconnected, then G itself is called a block (Harary 1994, p. 26) or a biconnected graph (Skiena 1990, p. 175).

 

Skiena, S. “Biconnected Components.” §5.1.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 175-177, 1990.

The coarseness xi(G) of a graph G is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph G. The coarseness of a planar graph G is therefore xi(G)=0.

The number of nodes in a graph is called its order.

A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with n=1, 2, … nodes are 1, 2, 4, 11, 33, 142, 822, 6966, 79853, … (OEIS A005470; Wilson 1975, p. 162), the first few of which are illustrated above.

  • TBA

GT – Matchings

Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

        • Matching
        • Maximal Matching
        • Maximum Matching
        • Perfect Matching

  • TBA at mathworld

 

References and further reading list: