Characteristic Polynomials of Adjacency Matrices of Families of Graphs

From CanisiusmathWiki

Any graph - even multigraphs and graphs with loops, can be viewed as an $n\times n$ matrix $Α$ with $α i, j = 1$ if $v_i\sim v_j$ and $α i, j = 0$ otherwise. This is called the adjacency matrix. This can be generalized to multigraphs by letting $α i, j =$ the number of edges between $v i$ and $v j$ . We can even examine hypergraphs by converting them to line graphs, and then constructing the adjacency matrix. The majority of the work here is on graphs with no multiple edges. By taking the characteristic polynomial of the adjacency matrix, we can use algebra to explore certain properties and similarities of graphs and graph families.

The roots of this characteristic polynomial are known as the spectrum (or eigenvalues) of the matrix (or of the graph); differing graphs with the same characteristic polynomial (and so the same roots) are known as Isospectral Graphs.

Table of contents

8 Products of Graphs and NEPS

[edit]

Methods/Tools

Mathematica has a Combinatorics package with lots of useful graph theoretic tools, but you have to load it in separately to use some of the functions we call in this section. Here's how:

- Go to this page on combinatorica.com (http://www.cs.uiowa.edu/~sriram/Combinatorica/NewCombinatorica.m)

- Edit->Select All, Edit->Copy

- Open Mathematica, Edit->Paste, Enter (wait for this to process - should take a minute or so)

- In the dialogue box, type <<DiscreteMath`Combinatorica` and press Enter

Some of these results can be (and were) found by hand, the process of taking the determinant by expansion by minors leading to naturally occurring recursion.

For less apparent familial patterns, try Factor[CharacteristicPolynomial[ToAdjacencyMatrix[Graph], x]].

In particular, for Graph, try types CompleteGraph[n], Path[n], and Cycle[n].

To generate large data sets quickly in Mathematica: For[i = 2, i < k, i++, Print[i , ",", Factor[CharacteristicPolynomial[ToAdjacencyMatrix[Graphtype[i]], x]]]], where of course you can fill in k with how large you'd like to go and GraphType with the type of Graph (Cycle, CompleteGraph, ...).

Combinatorica` has a Spectrum[Graph] function which takes graphs as input and finds the eigenvalues - see MathWorld (http://mathworld.wolfram.com/GraphSpectrum.html) for details.

[edit]

Complete Graphs

$K n$

The characteristic polynomial of $K n$ 's adjacency matrix is

$(x + 1) n - 1 (x - (n - 1))$ ,

implying eigenvalues of $n - 1$ (with degree 1) and $- 1$ (with degree $n - 1$ ).

Proof to come

$K n, m$

The characteristic polynomial for the adjacency matrix for regular complete bipartite simple graphs, $K n, n$ , is given by $x 2(n - 1) (x 2 - n 2)$ .

The general formula for the adjacency matrix, which holds for irregular complete bipartite graphs, $K n, m$ , is given by $( - 1) n + m x n + m - 2 (x 2 - n m)$ .

This implies the eigenvalues of 0 and the positive and negative square roots of nm.

Proof to come?

$K_{n_1, n_2, ..., n_k}$

Your genius goes here!

[edit]

Paths

Directed Paths

See Applications of Covering Maps to Spectral Theory of Graphs

Undirected Paths

The above link delves into this some, but there's more to look into.

- By Cor. 2.7 on pg. 10 of Biggs' Algebraic Graph Theory, as $P n$ has diameter $n - 1$ , all its eigenvalues will be distinct.

On page 11, Biggs gives the closed form of these in terms of Chebyshev Polynomials (http://en.wikipedia.org/wiki/Chebyshev_polynomials) of type 2 ( $C h a r (P n) = U n (x / 2)$ ), but Prof. Bisson says that nobody really yet knows why the two are related.

[edit]

Cycles

Directed Cycles

For a graphs with n vertices: $C h a r (D C n) = x n - 1$

Proof to come

Undirected Cycles

We're finding really cool patterns here, still need to follow through but planning on doing so right now. Here's what our train of thought was:

- Cycle patterns by themselves are weird.

- Look at prime cycles, as the characteristic polynomial of a graph divides the characteristic polynomials of its covers - in particular, cycles of degree pk cover cycles of degree p (for p prime), and maybe the rest of the polynomials will fall out of there (as, for example, 3*5=15).

So we did! It was awesome. Check out Data on Characteristic Polynomials of Cycles for more info.

- By Cor. 2.7 on pg. 10 of Biggs' Algebraic Graph Theory, as $C n$ has diameter $\left \lfloor \frac{n-1}{2} \right \rfloor$ , its spectrum contains at least $\left \lfloor \frac{n+1}{2} \right \rfloor$ distinct eigenvalues.

- Furthermore, cycles are distance-regular, implying by Prop. 21.1 on pg. 165 of Biggs that this inequality is an equality.

The closed form of these is closely related to Chebyshev Polynomials (http://en.wikipedia.org/wiki/Chebyshev_polynomials) of type 1 ( $T n$ ), but nobody really yet knows why the two are related.

[edit]

Hypercubes

$C h a r (Q 0) = x$

$C h a r (Q 1) = (x - 1)(x + 1)$

$C h a r (Q 2) = (x - 2)(x + 2) x 2$

$C h a r (Q 3) = (x - 3)(x + 3)(x - 1) 3 (x + 1) 3$

$C h a r (Q 4) = (x - 4)(x + 4)(x - 2) 4 (x + 2) 4 x 6$

There is a graph (http://mathworld.wolfram.com/HoffmanGraph.html) isospectral to $Q 4$

$C h a r (Q 5) = (x - 5)(x + 5)(x - 3) 5 (x + 3) 5 (x - 1) 10 (x + 1) 10$

$C h a r (Q 6) = (x - 6)(x + 6)(x - 4) 6 (x + 4) 6 (x - 2) 15 (x + 2) 15 x 20$

The general case seems to be (though we have no proof yet),

$Char(Q_n)=(x-n)(x+n)(x-n+2)^n(x+n-2)^n(x-n+4)^{{n \choose 2}}(x+n-4)^{{n \choose 2}}\ldots(x-1)^{{n \choose \lfloor n/2 \rfloor}}(x+1)^{{n \choose \lfloor n/2 \rfloor}}$ , for $n$ odd and

$Char(Q_n)=(x-n)(x+n)(x-n+2)^n(x+n-2)^n(x-n+4)^{{n \choose 2}}(x+n-4)^{{n \choose 2}}\ldots(x)^{{n \choose n/2}}$ , for $n$ even.

[edit]

Line Graphs

We can take the line graph $L (G)$ of any graph by defining a new graph where each edge of G corresponds to a vertex of L(G) and adjacency in L(G) is determined by coincidence of edges in G.

This process can be applied to Hypergraphs to obtain a graphical interpretation, which can then be analysed with typical algebraic graph theoretic methods - we hope to find connections between graphs and their line graph and generalize to analysis of hypergraphs via their line graphs.

[edit]

Connections

Using Cycle Spectra to Determine Path Spectra:

We have a theorem that the spectrum of a graph will be interlaced by the spectra of any subgraph induced by the removal of a single vertex.

Note: Removing any one vertex from $C n$ gives $P n - 1$ . Removing an endpoint from $P n$ will also give $P n - 1$ , but this may not be as useful for the following:

As from above hypothesis that every odd prime cycle's characteristic polynomial factors into $(x - 2)$ and a squared term, every cycle will have at least one repeated root for each distinct prime factor excluding 2. This implies a guaranteed specific eigenvalue for each distinct prime factor (excluding 2) of n for $P n - 1$ , as the eigenvalues interlace.

[edit]

Products of Graphs and NEPS

Upon understanding the general form of the characteristic polynomials and their resulting spectra for various families of graphs, we became interested in observing the effects on these properties of the respective graphs when their product is taken with other graphs. One way of thinking about these products is referred to as NEPS, or non-complete extended p-sums, which are described in depth in the book Spectra of Graphs by Cvetkovic and Sachs.

There are various forms of products which can be taken on graphs, some of which include the direct product, box product, strong product, and lexicographic product. These products retain different properties of the original graphs and are used for different purposes in graph theory. We will first examine the direct product.

Let G and H be graphs with vertices $(x 1, x 2,..., x n)$ and $(y 1, y 2,..., y m)$ , respectively. We then define the direct product of G and H to be the graph $G \times H$ where $V(G \times H)=V(G) \times V(H)$ and $(x_i,y_i) \to (x_j,y_j)$ if $x_i \to x_j$ and $y_i \to y_j$ . The result of the direct product on the adjacency matrices of the graphs is given by taking the Kronecker product of the adjacency matrices of G and H. Additionally, it is known that if the eigenvalues for G and H are $(λ 1,λ 2,...,λ n)$ and $(μ 1,μ 2,...,μ m)$ , respectively, then the resulting eigenvalues of $G\times H$ are

$(λ 1 μ 1,...,λ 1 μ m,...,λ n μ 1,....λ n μ m)$

The NEPS method, mentioned above, takes the direct product through a slightly different way. In this method, as before, the resulting graph has vertices formed by the Cartesian product of the sets of vertices of graphs $G 1, G 2,..., G n$ , in our case being only graphs G and H with vertices $(x 1, x 2,..., x n)$ and $(y 1, y 2,..., y m)$ , respectively. To indicate how the product should be taken, an n-tuple basis, $β 1,β 2,...,β n$ , is given which is filled with either 0's or 1's. Then, two vertices $(x i, y i)$ and $(x j, y j)$ are adjacent if and only if in the basis $Β$ there is an n-tuple $β$ such that $x i = y i$ holds when $β i = 0$ and $x_j \to y_j$ when $β j = 1$ . The basis $β$ for the direct product is $β = (1,1)$ .

The figure below shows an illustration of the graphs G and H, which are the complete graph K2 and the path graph P3.

Description

(then insert picture of direct product!!)

The next product we considered is commonly referred to as the box product, or $G \Box H$ . We define the box product of G and H to be the graph $G \Box H$ where $V(G \Box H) = V(G) \times V(H)$ and $(x_i,y_i) \to (x_j,y_j)$ if $x i = x j$ and $y_i \to y_j$ and $y i = y j$ and $x_i \to x_j$ .