Isospectral Graphs

From CanisiusmathWiki

Table of contents

Strategy

My strategy is to gather as much information about a graph as possible from the characteristic polynomial of the graph's adjacency matrix. Then, it should be easy to generate isospectral graphs.

Putting Pictures of Graphs on the Wiki

[edit]

Findings

Note: uncited findings are original findings from our research, and anyone is welcome to add a proof or make changes.

1. A term of $(x - n)$ will appear in the characteristic polynomial when:

(a) every vertex of a graph has $n$ edges directed away and $n$ edges directed toward it, or

(b) the graph contains a disjoint subgraph satisfying condition (a).

2. The characteristic polynomial of the disjoint union of two graphs will be the product of their characteristic polynomials.

3. Asymmetries in a graph correspond to large, unfactorable polynomial factors of its characteristic polynomial.

4. For $G i$ the induced subgraph on $G$ without vertex $i$ , the derivative of the characteristic polynomial on G

$Char'(G)=\sum_{i=1}^nChar(G_i)$ (Biggs, 11)

With this in mind, look at what previous REU groups did with the Figure Equation.

5. The characteristic polynomial of a complete graph with n vertices, $K n$ , is: $(x + 1) n - 1 (x - (n - 1))$ . See: Characteristic Polynomials of Adjacency Matrices of Families of Graphs

[edit]