Here's a list of 21 edge-transitive graphs on 6 vertices.
"E???" # 6 K_1
"E_??" # K_2 + 4
"Eo??" # S_2 + 3
"Ew??" # K_3 + 3
"Es??" # S_3 + 2
"Es_?" # S_4 + 1
"Esa?" # S_5
"E`??" # 2 K_2 + 2
"Er??" # C_4 + 2
"E~??" # K_4 + 2
"Elg?" # K_{3,2} + 1
"Ehc?" # C_5 + 1
"E~{?" # K_5 + 1
"E`__" # 2 S_2
"Eli_" # K_{4,2}
"E`oo" # 2 K_3
"E`?G" # 3 K_2
"EpOW" # C_6
"Ezuw" # Octahedron
"E~~w" # K_6
"ErYW" # K_{3,3}
K_n: complete graph on n vertices
C_n: n-cycle
S_n: n-star on n+1 verts
K_{m,n}: complete bipartite graph between m and n vertices
X + t: the graph X with t extra independent vertices
tX: t disjoint copies of X
They've all got 6 vertices. They're all edge transitive. That means
Weisstein's list is wrong.
Also, I tried to use your code to check if a random 100 vertex graph
with 100 edges was edge-transitive. It took more than a minute, and I
killed it. The already-implemented
G.line_graph().is_vertex_transitive() finished in 26 ms.
On Mon, Oct 29, 2012 at 12:37 PM, Jernej Azarija <azi.std...@gmail.com> wrote:
> This works yes. However it still leaves open what is going on with
> disconnected graphs and what is the problem with the proposed
> is_edge_transitive method!
>
> Do you (or anyone) happens to see a bug or a bizarre mistake in the
> implementation?
>
> On Monday, 29 October 2012 20:02:40 UTC+1, Tom wrote:
>>
>> Sorry, I meant n=8.
>>
>> sage: print [ec(n) for n in range(9)]
>> [1, 1, 1, 2, 3, 4, 6, 5, 8]
>>
>> On Mon, Oct 29, 2012 at 11:41 AM, Tom Boothby <tomas....@gmail.com> wrote:
>> > Wanna run that on connected graphs? I get the correct sequence out to
>> > n=9 for
>> >
>> > def ec(n)
>> > c = 0
>> > for g in graphs(n):
>> > if g.is_connected() and g.line_graph().is_vertex_transitive():
>> > c+= 1
>> > return c
>> >
>> >
>> >
>> > On Mon, Oct 29, 2012 at 11:37 AM, Jernej Azarija <azi.s...@gmail.com>
>> > wrote:
>> >> Hello!
>> >>
>> >> Yes but this appears to be even more bogus. Consider this:
>> >>
>> >> ==
>> >> def ec(n):
>> >> c = 0
>> >> for el in graphs.nauty_geng(str(n)):
>> >> if (el.line_graph()).is_vertex_transitive():
>> >> c+=1
>> >> return c
>> >> ==
>> >>
>> >> sage: ec(7)
>> >> 27
>> >> sage: ec(8)
>> >> 39
>> >>
>> >> But there are 26 and 40 edge-transitive graphs on 7 and 8 nodes
>> >> respectively. It appears as if something is wrong with the computation
>> >> of
>> >> the automorphism group of a graph.
>> >>
>> >> Can someone comment on that?
>> >>
>> >>
>> >>
>> >>
>> >>
>> >>
>> >>
>> >>
>> >> On Monday, 29 October 2012 19:29:56 UTC+1, Tom wrote:
>> >>>
>> >>> I use G.line_graph().is_vertex_transitive()
>> >>>
>> >>> On Mon, Oct 29, 2012 at 7:12 AM, Jernej Azarija <azi.s...@gmail.com>
>> >>> wrote:
>> >>> > Hello!
>> >>> >
>> >>> > I am slowly implementing a patch that will provide some features for
>> >>> > symmetry testing of graphs.
>> >>> >
>> >>> > However I am already puzzled by the following attempt at testing for
>> >>> > edge-transitive graphs. Here is a straightforward textbook
>> >>> > implementation
>> >>> > (the presented code omits the exceptional treatment of the singleton
>> >>> > graph)
>> >>> >
>> >>> > ===
>> >>> > def is_edge_transitive(self):
>> >>> >
>> >>> > A,T = self.automorphism_group(translation=True)
>> >>> > for (x,y,_) in self.edges():
>> >>> > acts = set([])
>> >>> > for g in A:
>> >>> > a,b = g(T[x]),g(T[y])
>> >>> > acts.add((a,b) if a < b else (b,a))
>> >>> > if len(acts) == self.size():
>> >>> > return True
>> >>> > return False
>> >>> > ===
>> >>> >
>> >>> > Testing the code (Petersen, Gray and path graph) it appears as if
>> >>> > the
>> >>> > results are correct. But considering the following function
>> >>> > computing
>> >>> > the
>> >>> > number connected edge transitive graphs of given order
>> >>> >
>> >>> > ===
>> >>> > def ecc(n):
>> >>> > c = 0
>> >>> > for el in graphs.nauty_geng(str(n)+ " -c "):
>> >>> > if el.is_edge_transitive():
>> >>> > c+=1
>> >>> > return c
>> >>> > ===
>> >>> >
>> >>> > we observe that
>> >>> >
>> >>> > sage: [ecc(i) for i in xrange(2,9)]
>> >>> > [1, 2, 3, 4, 6, 5, 8]
>> >>> >
>> >>> > which does not coincide with the data provided at oeis:
>> >>> > http://oeis.org/A095424/list . The difference gets even bigger if we
>> >>> > count
>> >>> > all edge-transitive graphs instead of just connected.
>> >>> >
>> >>> > Anyone happens to see the flaw in the is_edge_transitive method?
>> >>> >
>> >>> > Best,
>> >>> >
>> >>> > Jernej
>> >>> >
>> >>> > --
>> >>> > You received this message because you are subscribed to the Google
>> >>> > Groups
>> >>> > "sage-devel" group.
>> >>> > To post to this group, send email to sage-...@googlegroups.com.
>> >>> > To unsubscribe from this group, send email to
>> >>> > sage-devel+...@googlegroups.com.
>> >>> > Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>> >>> >
>> >>> >
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> >> Groups
>> >> "sage-devel" group.
>> >> To post to this group, send email to sage-...@googlegroups.com.
>> >> To unsubscribe from this group, send email to
>> >> sage-devel+...@googlegroups.com.
>> >> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>> >>
>> >>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To post to this group, send email to sage-devel@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-devel+unsubscr...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
