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<javascript:>>
> 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<javascript:>.
>
> > To unsubscribe from this group, send email to
> > sage-devel+...@googlegroups.com <javascript:>.
> > 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.
