Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to McKay in McKay, Brendan; Royle, Gordon F.; The transitive graphs with at most $26$ vertices. Ars Combin. 30 (1990), 161-176., there are exactly 2 isomorphically distinct graphs with 8 vertices and 3 edges per vertex (Table 2: pg 175). I've been able to find one of these on my own:

vertex_tran_8_3

What is the other graph mentioned here, and more importantly, how do you find this graph without explicit enumeration?

share|improve this question
1  
Switch the "cross" for a "parallel"; gives you an octogon with 2 rectangles inscribed in it. How did I find it? I just looked at your picture long enough. I am not a pro in graph theory though ; maybe they're isomorphic but I can't see it. Perhaps you could look into that. –  Patrick Da Silva Feb 15 '12 at 21:10
    
"Three vertices per node"? I had thought that nodes and vertices are the same thing---just two different names for it. Could you have meant three edges per vertex (or---what is the same thing---three edges per node)? –  Michael Hardy Feb 16 '12 at 1:22
    
@MichaelHardy, that's correct - editing. –  Hooked Feb 16 '12 at 4:17

2 Answers 2

up vote 1 down vote accepted

Hm. Like in my comment, I am not sure that my suggestion is the good one, but here's my try :

Take your drawn graph as the first one (which is an amazing picture by the way, good job for putting it there) and define the second graph which is the same but replace $3-2$ by $3-6$ and $6-7$ by $2-7$ (undo the cross, make it parallels). In other words, my new graph would have the edges $$ \{0-1, 1-2, \dots, 6-7,7-0, 0-4, 1-5, 3-6, 2-7\}. $$

EDIT: Ok here's a proof that they're not isomorphic : your graph has a $5$-cycle ($3-4-5-6-2-3$). My graph doesn't have such a luxury : the sets $A= \{0,2,3,5\}$ and $B=\{1,4,6,7\}$ have the property that every time you travel from a vertice to another using an edge, you must go either from $A$ to $B$ or from $B$ to $A$. Therefore you cannot go back to $A$ in $5$ steps (i.e. a cycle of the form $a-b-c-d-e-f$ will be such that $a \in A \Longleftrightarrow f \in B$, so that $a \neq f$ and this is not a $5$-cycle).

Since this last argument shows that every cycle in my new graph has even length, we could've also used the fact that your graph has a $7$-cycle $(3-2-6-5-1-0-7-3)$.

Hope that helps,

share|improve this answer
    
How do you denote an "edge"? I'm curious. I don't remember any standard notation for this! –  Patrick Da Silva Feb 15 '12 at 21:17
    
Or a "cycle"... that would be useful too –  Patrick Da Silva Feb 15 '12 at 21:37
1  
Edges are usually denoted $(a, b)$ or sometimes $\{a, b\}$ if the graph is undirected. Knuth uses the same notation you do though---for edges and cycles. –  Zach Langley Feb 16 '12 at 3:43

I think there are 5, not 2, isomorphism classes of connected 3-regular graphs on 8 vertices (see https://oeis.org/A002851). But your title has the word "transitive". I don't know what that means, but maybe with that additional qualification there are only two.

EDIT: The vertex-transitive ones are pictured at http://mathworld.wolfram.com/CubicVertex-TransitiveGraph.html

share|improve this answer
    
Transitive means that the automorphism group of the graph acts transitively on the graph. (Wikipedia quote here.) Perhaps someone could shed some light on intuition about this? –  Patrick Da Silva Feb 16 '12 at 3:55
    
The five cubic graphs on 8 vertices are here: imm.io/gDDQ –  utdiscant Feb 16 '12 at 7:24
    
@GerryMyerson thanks for the mathworld link - it appears that the graph shown above is the 4-Mobius ladder graph and the one mentioned by Patrick is the Cubical graph. It's nice to know they have names! –  Hooked Feb 16 '12 at 14:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.