No, arc-transitivity is quite easy:
G.to_directed().line_graph().is_vertex_transitive()
Are you saying that the graph with 6 vertices and no edges is not a
graph? What about the graphs on 1,2,..5 vertices and no edges?
Because those are all counted in OEIS. Even on Mathworld, it says
"Counting empty graphs as edge-transitive, the numbers of
edge-transitive graphs on n=1, 2, ... nodes are 1, 2, 4, 8, 12, 21,
27,..."
Stranger yet, sage counts 39 edge-transitive graphs, where OEIS
currently lists 40. So yes, I'll be getting independent verification
before submitting a correction to OEIS.
On Tue, Oct 30, 2012 at 12:36 AM, Jernej Azarija <azi.std...@gmail.com> wrote:
>
>
> On Monday, 29 October 2012 22:49:03 UTC+1, Tom wrote:
>>
>> 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.
>
>
> Hello,
>
> thank you for your help Tom!
>
> I am not sure 6K_1 counts since it has no edges. Can we test the program in
> mathematica or some other program to be 100% sure before we warn oesis?
>
>>
>>
>> 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.
>
> Indeed this version is very very slow compared to the testing of vertex
> transitive graphs. But nonetheless it is useful since at some point I will
> implement a test for arc-transitivity (symmetric graphs) and there is no
> useful way to convert the problem to vertex transitivity. So the question on
> why the code is not correct remains!
>
>>
>>
>> On Mon, Oct 29, 2012 at 12:37 PM, Jernej Azarija <azi.s...@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-...@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.
