Timeline for Is the following graph well known?
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2011 at 5:12 | comment | added | Aaron Meyerowitz | The regularity conditions can hold with out there actually being automorphisms, then the graph is said to be distance regular. There is one example (of a distance regular but not distance transitive) graph with degree 3. It has 126 vertices and (thus) 189 edges. | |
| Jan 6, 2011 at 5:11 | comment | added | Aaron Meyerowitz | In a distance transitive graph the number of associate classes is the diameter (plus one). In a power $A^k$ (or polynomial $f(A)$) of the adjacency matrix the value of the $(u,v)$ entry depends only on the associate class. So looking at $A^k$ can reveal the associate classes. I am being imprecise here. An association scheme is any partition of the pairs subject to certain conditions. I am (as is usuual) calling that scheme with the fewest classes the association scheme of the graph. | |
| Jan 6, 2011 at 3:09 | comment | added | Tyson Williams | Let me make sure I am following. Let $A$ be the adjacency matrix of a undirected, simple, regular graph $G$. Then the number associate classes of $G$ is the maximum number of distinct non-zero elements in $A^i$ for all $i > 0$. If the number of associate classes is 1, then the graph is distance-transitive. Is this correct? | |
| Jan 5, 2011 at 9:18 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
corrections
|
| Jan 5, 2011 at 7:13 | comment | added | Aaron Meyerowitz | Thanks. I added details on the eigenvalues for one graph. | |
| Jan 5, 2011 at 7:07 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
more detqails
|
| Jan 4, 2011 at 22:42 | comment | added | Tyson Williams | It appears that the graph family is not well known. This answer stated as much and was also helpful in understanding this graph family better. | |
| Jan 4, 2011 at 22:40 | vote | accept | Tyson Williams | ||
| Dec 21, 2010 at 21:00 | comment | added | Aaron Meyerowitz | Sorry, that was actually the distance 2 matrix (i.e. [1,2,3] connected to [1,4,5] & [1,4,2] & [1,3,2]) The correct eigenvalues and multiplicities are: [12, 1], [8, 12], [5, 6], [4, 15], [3, 28], [1, 30], [0, 14], [-3, 104] | |
| Dec 21, 2010 at 16:34 | comment | added | Aaron Meyerowitz | I don't recall. As a test case, (which I did not do before) PP(7,3) has 210 vertices, diameter 3, and eigenvalues.....(time to write a program)...[63, 1], [16, 12], [7, 6], [3, 104], [-3, 14], [-5, 30], [-9, 28], [-11, 15] (that is to say that 3 is an eigenvalue of multiplicity 104). I did that in the simplest way possible (let Maple use 1 minute of my time 48M of memory and 3 sec of computing on a 210 by 210 0,1 matrix). With more thought on my side it should be possible to do PP(n,3) with a symbolic 8 x 8 matrix . | |
| Dec 21, 2010 at 13:54 | comment | added | Tyson Williams | What cases have you tested? What are the eigenvalues? | |
| Dec 19, 2010 at 0:31 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
added 270 characters in body; added 6 characters in body
|
| Dec 17, 2010 at 4:34 | history | answered | Aaron Meyerowitz | CC BY-SA 2.5 |