Talk:Symmetric graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Importance
 Field:  Discrete mathematics


I have reworded the article to agree with the definition in the cited references. Radagast3 (talk) 08:38, 26 March 2009 (UTC)

The wording "a graph is symmetric if its automorphism group acts transitively upon ... edges considered as having a direction" covers the fact that in Wikipedia directed edge currently refers to an edge in a directed graph, and other words are needed. Radagast3 (talk) 09:50, 27 March 2009 (UTC)

Arc-transitive graph currently redirects here, since the major texts use the words as synonyms. Radagast3 (talk) 09:54, 27 March 2009 (UTC)

I have added a clarifying para regarding the confusion over the term "symmetric." I think following Biggs (symmetric = arc-transitive) is the best course of action here (as we have done during the expansion of related articles since March), since arc-transitivity is the more important concept. I note that the MathWorld definition is a complete dog's breakfast, trying to equate two different definitions, and then giving an example where they differ. — Radagast3 (talk) 03:32, 4 September 2009 (UTC)
That material was already present two paragraphs up. I merged your new paragraph with the old one. Apparently vertex-transitive + edge-transitive is also called (less ambiguously) half-transitive. —David Eppstein (talk) 03:39, 4 September 2009 (UTC)
Thanks! Goes to show the danger of poorly-thought-out edits. I even wrote the material two paragraphs up. — Radagast3 (talk) 03:59, 4 September 2009 (UTC)
The main fact is that everybody is interested in cubic symmetric graphs. And for cubic graphs there is an equivalence beetween "vertex-transitive + edge-transitive" and "arc-transitive". In fac a half-transitive graph which is not symmetric need to be of even degree. Koko90 (talk) 07:24, 4 September 2009 (UTC)
Yes, as you say, the equivalence for cubic graphs makes the difference between "vertex-transitive + edge-transitive" and "arc-transitive" unimportant for the cubic case. However, it is important that the collection of definitions in Wikipedia be consistent, and there are some other important properties about arc-transitive graphs. — Radagast3 (talk) 08:08, 4 September 2009 (UTC)
I agree, definitions in Wikipedia need to be consistent.Koko90 (talk) 08:55, 4 September 2009 (UTC)

Similarly, this article makes two references to "linked" vertices. Unless this is a concept I haven't come across, this should be replaced by the more common term "adjacent". Or if u and v linked means there exists a u-v path, then we need to talk about u and v being in the same connected component or something like this. Triangl (talk) 18:47, 6 January 2011 (UTC)

A "half-transitive" article?[edit]

I'm wondering if we should have an article on half-transitive graphs. It would literally say only:

A half-transitive graph is one that is vertex-transitive and edge-transitive. Every connected symmetric graph must be half-transitive, and half-transitive graphs of odd degree are always symmetric, but there exist graphs that are half-transitive yet not symmetric. The smallest half-transitive but not symmetric graph is Holt's graph, with degree 4 and 27 vertices.

If yes, we should probably update the template, and create a picture of Holt's graph to use as an illustration. If no, we should probably change the red link in this article to a bold. I'm currently leaning towards "no," since there's just not enough to say about half-transitive graphs. — Radagast3 (talk) 00:37, 5 September 2009 (UTC)

Google scholar finds 29 articles on half-transitive graphs. That seems like enough to say more than that short paragraph about them. —David Eppstein (talk) 00:38, 5 September 2009 (UTC)
Possibly, although much of that material might not be at the right level for Wikipedia. A revised template would look like this, I think:
Radagast3 (talk) 00:49, 5 September 2009 (UTC)
Graph families defined by their automorphisms
distance-transitive distance-regular strongly regular
symmetric (arc-transitive) t-transitive, t ≥ 2 skew-symmetric
(if connected)
vertex- and edge-transitive
edge-transitive and regular edge-transitive
vertex-transitive regular (if bipartite)
Cayley graph zero-symmetric asymmetric
Yes, we need a "half-transitive" article. By the way, i will write an article about the Holt's graph and draw a few illustration as soon as possible. PS : for the templaye you can add semi-symmetric (with only one arrow, semi-symmetric -> edge-transitive and regular). Koko90 (talk) 07:50, 5 September 2009 (UTC)
I have updated the template, and created the half-transitive graph article, since we have two strong votes for it. I will be very grateful, Koko90, if you will handle Holt's graph.
The "edge-transitive and regular" entry in the table actually clicks to "semi-symmetric".
Radagast3 (talk) 08:54, 5 September 2009 (UTC)
The problem with "semi-symmetric" is that a "edge-transitive and regular" graph is not "semi-symmetric" if it is symmetric. A semi-symmetric graph, by definition, can't be symmetric. It is a edge-transitive and regular graph that is not vertex transitive. Koko90 (talk) 09:23, 5 September 2009 (UTC)
I understand exactly what you mean, and the same thing has now happened with half-transitive: the table entry is not quite the same as the article pointed to. I'm not sure how to resolve this (there's a limit to how much we can squeeze into the table), so I'm tempted to leave things as they are until inspiration strikes. — Radagast3 (talk) 09:47, 5 September 2009 (UTC)
The "edge-transitive and regular" / "semi-symmetric" entry in the table is David's by the way, so he might be able to further explain it, but it seems a reasonable response to conflicting issues (the definition of a class that's "A" but not "B", and the limited space in the table). — Radagast3 (talk) 09:51, 5 September 2009 (UTC)
Actually, I've had to make a few changes: checking the reference I see we got the definition wrong. — Radagast3 (talk) 09:19, 5 September 2009 (UTC)
The article on Holt's graph should probably be Holt graph for consistency... I'll start a stub. — Radagast3 (talk) 13:23, 6 September 2009 (UTC)

Table of examples[edit]

The table {{Graph families defined by their automorphisms}} is excellent. I was wondering if we could have a larger version of the same table somewhere, with an illustration for each of the families? (Just one "representative" example of a graph per family.) Or do we already have something like? I am not sure where it would belong, perhaps somewhere near Graph automorphism#Graph families defined by their automorphisms? — Miym (talk) 11:02, 5 September 2009 (UTC)

It's a good idea. It's not entirely obvious which examples to use... they would need to be fairly small in order to fit, but would also have to be chosen to be a member only of the selected table entry. Possibilities include:
The Cayley graph for the group .
1. Distance-transitive graph: want an example which is not strongly regular, so not the Petersen graph.
2. Symmetric graph: perhaps the Möbius–Kantor graph, which is not distance-transitive.
3. Vertex- and edge-transitive: perhaps Holt's graph, which is half-transitive, i.e. not symmetric.
4. Edge-transitive and regular: perhaps the Folkman graph or the Gray graph, which are semi-symmetric.
5. Edge-transitive graph: perhaps K2,3 or similar, which is not regular.
6. Vertex-transitive graph: want an example which is not edge-transitive and not a Cayley graph.
7. Regular graph: perhaps the Frucht graph, which is not vertex-transitive.
8. Cayley graph: perhaps the one on the right.
9. Strongly regular graph: want an example which is not distance-transitive,
10. Distance-regular graph: want an example which is not distance-transitive or strongly regular.
Radagast3 (talk) 11:42, 5 September 2009 (UTC)

Perhaps something like this (as yet incomplete and with formatting problems):

(the table that was here has been moved to Graph automorphism#Graph families defined by their automorphisms, even though it is still incomplete).

Radagast3 (talk) 23:10, 5 September 2009 (UTC)

Updated table. — Radagast3 (talk) 04:14, 6 September 2009 (UTC)
Moved table to Graph automorphism#Graph families defined by their automorphisms. It still needs images for:
a. Distance-regular graph: ideally, want an example which is not distance-transitive or strongly regular.
b. Vertex- and edge-transitive: perhaps Holt's graph, which is half-transitive, i.e. not symmetric.
c. Vertex-transitive graph: ideally, want an example which is not edge-transitive and not a Cayley graph.
Radagast3 (talk) 05:21, 6 September 2009 (UTC)

Many thanks, looks great! I was wondering if we should also add some figure captions, like in the example below?

  1. It might avoid some confusion (we are not showing "the regular graph" but just the Frucht graph which is a regular graph).
  2. For an interested reader, we would have links to pages which explain the illustration (and, hopefully at least in future, also explain why the particular graph is classified the way it is).

(Or does it look too messy? Another possibility might be to have footnotes with similar links and further explanations.) A related comment: it might be a good idea if, e.g., Edge-transitive graph had an illustration of the same example K3,2 as what we have in the table; then a reader who clicks on Edge-transitive graph instead of K3,2 would also see a familiar-looking example, and the figure caption on that page would provide more details, e.g., explaining that the graph is edge-transitive and not regular. — Miym (talk) 11:50, 6 September 2009 (UTC)

Arrow east.svg
Arrow west.svg
distance-transitive distance-regular strongly regular
Arrow south.svg
Arrow west.svg
symmetric (arc-transitive) t-transitive, t ≥ 2
Arrow south.svg
(if connected)
Disc Plain grey.svg
Arrow east.svg
Arrow east.svg
vertex- and edge-transitive edge-transitive and regular edge-transitive
Arrow south.svg
Arrow south.svg
Arrow east.svg
vertex-transitive regular
Arrow north.svg
Cayley graph for Z2 × Z3
Cayley graph
Hmmm. I like the idea in principle, but it does seem to make the table too cluttered. I've tried something more subtle instead. Possibly too subtle.
As to changing the pointed-to articles to match... it's worth thinking about, but I'm sure the images already in those articles are well-chosen.
Radagast3 (talk) 12:14, 6 September 2009 (UTC)

The current version looks like a good compromise to me. It just bothers me a bit that the tooltips of the figures are "#" which isn't that informative. Here is an attempt to create a simple version with little clutter and with useful tooltips. Here each image has a tooltip that contains the name of the graph, and each image is a link to the relevant article about the graph. (Note that in this version the tooltips don't have to match the names of the target pages – e.g., "Skeleton of the dodecahedron" vs. "Dodecahedron" – so it's possible to include some extra information in the tooltips for the benefit of those who happen to notice them.) — Miym (talk) 13:00, 6 September 2009 (UTC)

Skeleton of the dodecahedron
Arrow east.svg
Shrikhande graph
Arrow west.svg
Paley graph
distance-transitive distance-regular strongly regular
Arrow south.svg
F26A graph
Arrow west.svg
Nauru graph
symmetric (arc-transitive) t-transitive, t ≥ 2
Arrow south.svg
(if connected)
Holt's graph
Arrow east.svg
Folkman graph
Arrow east.svg
Complete bipartite graph K3,2
vertex- and edge-transitive edge-transitive and regular edge-transitive
Arrow south.svg
Arrow south.svg
Skeleton of the truncated tetrahedron
Arrow east.svg
Frucht graph
vertex-transitive regular
Arrow north.svg
Skeleton of the triangular prism
Cayley graph
Looks great! – Radagast3 (talk) 13:12, 6 September 2009 (UTC)
I observe that the graph appearing (twice) above and described as a "Cayley graph" is not a Cayley graph. Cayley graphs are directed. This does not matter much for the red edges (there's a convention that an undirected edge connected to no other edge of the same color means a two-cycle of that color). But depending on the direction of the black edges, it might by a Cayley graph for Z2 × Z3, or for the dihedral group of order 6. Maproom (talk) 07:04, 5 May 2015 (UTC)

Case of the oriented graphs[edit]


This article apparently applies to unoriented graphs. But, as the German page states it,

"Als symmetrischen Graph bezeichnet man in der Graphentheorie einen gerichteten Graphen, bei dem zwischen zwei seiner Knoten jeweils entweder keine (gerichtete) Kante verläuft oder aber Kanten in beide Richtungen verlaufen."

a "symmetric graph" can also be an oriented graph where two vertices are either unconnected or connected in both directions.

This definition of a symmetric graph boils down to the definition of an unoriented graph, but it is nevertheless used in the math literature. It's also the definition that appears on French wiktionnary. --MathsPoetry (talk) 21:23, 20 April 2012 (UTC)


This article uses the terms "2-transitive", "3-transitive", etc., in a way incompatible with most (maybe all) other sources. In other sources, such as the Mathieu group article, n-transitive is used, as defined here, in relation to sets of n points, and so is stronger than when used as in this article in relation to arcs of n points. Sources such as this use the term "n-arc-transitive" for transitivity in relation to arcs of n points.

I plan to edit all occurrences of "n-transitive" in the article to "n-arc-transitive", unless someone can explain why I shouldn't, citing sources that use the term as used here. Maproom (talk) 06:54, 5 May 2015 (UTC)