Factoring Graphs

A graph is a finite set X, called vertices, together with a set U of two element subsets, called edges. G = {X, U}.

An example is

Figure 1

The adjacency matrix of G is defined with each entry equal to the number of edges starting at and ending at .
For the above graph the adjacency matrix is

Graphs may be directed (called digraphs). Most of the ones we will work with are directed. An undirected edge implies that the path works in both directions, so, by itself, an undirected edge is equivalent to two directed and opposite edges, and is one cycle by itself.

| λ I – M | = (λ) is the characteristic polynomial, the roots of which are called the spectrum of G. They are also called the eigenvalues of the matrix. Here I is the identity matrix.

For the above graph (λ) = -3+1.

A cycle of length n is a closed path of that number of edges and vertices. A loop is a 1-cycle. For example the graph above has 4 cycles of length 2 since each undireted edge is a back and forth cycle of lenth 2. There are no other cycles since there are no other closed paths. (By the way, this polynomial does factor: -2+1-=- = (-λ -1)(+λ -1).

Figure 2

The number of loops equals the trace of the adjacency matrix. Since the sum of the roots of the characteristic polynomial is the Trace of the matrix, there can be no loops if the sum of the roots is zero.

The graph G is uniqely determined by the matrix A but not vice-versa. Graphs with the same ajacency matrix A are termed isomorphic and can be grouped in an equivalence class. To each G there is a class of adjacency matrices. (λ) is an invariant of this class (which means that they all created the same characteristic polynomial).

The coefficients of (λ)

Let

(1)

The values of all the can be found if all the directed cycles of G are known.

Coefficients theorem for digraphs

(2)

where is the set of all linear directed subgraphs of G with exactly i vertices.  P(L) denotes the number of cycles of which L is composed.

A linear directed graph has indegree 1 and outdegree 1 at each vertex. They are cycles or are composed of cycles. This is very neat.

Example from figure 1

There are 4 vertices so that the characteristic polynomial is of degree 4

(3)

= 0 since there are no subgraphs of 1 vertex with  one line coming in and one going out; i.e., there are no loops.

= -3  since each edge between two vertices is a cycle 2 with one line in and one line out.

= 0since there are no 3 cycles.

Determinents

Since for λ = 0   | λ I - A | = (λ) give |A| = , this can be a nice way to find certain determinants. The program is

1. Begin with a determinant of all positive elements.

2. Find the multigraph and .

Coloring a Graph

A graph is properly colored if each vertex is colored so that adjacent vertices (i.e., connected by an edge) are differently colored. G is k colorable if it can be properly colored by k colors. The chromatic number of G is k if G is k colorable but not k-1 colorable. A graph is bipartite if its chromatic number is 1 or 2.

The divisor concept

Let D = ()be the following m×n matrix. If it is possible to color G with m colors, then is the number of arcs that begin on each vertex of color i and terminate on color j. We say that this is a D-feasable coloration.

For undirected graphs, there is no relevance to front and rear.

A proper divisor satisfies D|G and has fewer vertices.

Symmetry and Divisors

A permutation acting on the vertices of G is called an automorphism if it is adjacency preserving (i.e., the same numbered vertices still have the same adjacency). In this case the adjacency matrix is unchanged. Γ(G) is the automorphism group of G.

Theorem: G is a strongly connected digraph and let Δ = (,, ,...,) be the system of orbits into which the vertices of G are partitioned by the symmetry Σ. The number of arcs terminating on from is . Then D is a proper front divisor.

This is not as scary as it sounds. The subgroup mentioned is the set of vertices that are equivalent under the symmetry.

Example: Figure 1

The symmetry of the graph is that 1 and 4 can be changed if 2 and 3 are simultaneously changed. Hence = (1, 4) and =(2,3) are equivalent. Here is the matrix. There is one line from group 1 to 2 and vice-versa. There is one from 2 to itself.

Out[13]//MatrixForm=

The characteristic polynomial is -λ -1.

Created by Mathematica  (November 6, 2005)