![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)
I'm wondering if we should have an article on half-transitive graphs. It would literally say only:
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)
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)
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)
Many thanks, looks great! I was wondering if we should also add some figure captions, like in the example below?
(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)
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)
![]() |
![]() |
![]() |
![]() |
![]() |
distance-transitive | distance-regular | strongly regular | ||
![]() |
||||
![]() |
![]() |
![]() |
||
symmetric (arc-transitive) | t-transitive, t ≥ 2 | |||
![]() |
||||
![]() |
![]() |
![]() |
![]() |
![]() |
vertex- and edge-transitive | edge-transitive and regular | edge-transitive | ||
![]() |
![]() |
|||
![]() |
![]() |
![]() |
||
vertex-transitive | regular | |||
![]() |
||||
![]() |
||||
Cayley graph |
Hello,
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)
The result of the move request was: consensus not to move the page as proposed at this time, per the discussion below. Thanks to all for their participation in the discussion. Dekimasu よ! 01:42, 20 April 2018 (UTC)
Symmetric graph →
Arc-transitive graph – This type of graph is usually called an
arc-transitive graph. A
symmetric graph can also be a graph that is both
vertex-transitive and
edge-transitive. The article also mentions
t-arc-transitive graphs, which are never called
t-symmetric graphs. Therefore, this page should be moved to
arc-transitive graph.
Math Maniac (
talk) 15:32, 8 April 2018 (UTC)--Relisting.
Dekimasu
よ!
18:21, 15 April 2018 (UTC)
I know that this discussion is finished, but I would like to point out that Maproom was wrong. The Holt graph is not arc-transitive by any definition. It is a graph that is vertex-transitive and edge-transitive, but not arc-transitive. By a common definition of symmetric graph, the Holt graph is symmetric. The fact that symmetric graph and arc-transitive graph have different meanings is the reason that this page should be moved. Math Maniac ( talk) 19:08, 28 July 2018 (UTC)
I just read the definition of a symmetric graph in the book Topics in Algebraic Graph Theory (Beineke and Wilson, eds., 2007).
That definition differs from the one in this article, because the book's definition requires not only that the automorphism group of a graph be transitive on edges, but also that it be transitive on vertices.
Are both definitions used currently by researchers? If so, the article should mention this fact.
Or is one of these definitions wrong?
Of course, for a graph G, IF for any two distinct vertices v and w ∊ G, both of [v,w] and [w,v] are always considered to be edges of G ... then transitivity on vertices would follow from transitivity on edges. 2601:200:C000:1A0:F8A4:C598:11E7:9879 ( talk) 17:56, 21 June 2022 (UTC)
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)
I'm wondering if we should have an article on half-transitive graphs. It would literally say only:
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)
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)
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)
Many thanks, looks great! I was wondering if we should also add some figure captions, like in the example below?
(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)
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)
![]() |
![]() |
![]() |
![]() |
![]() |
distance-transitive | distance-regular | strongly regular | ||
![]() |
||||
![]() |
![]() |
![]() |
||
symmetric (arc-transitive) | t-transitive, t ≥ 2 | |||
![]() |
||||
![]() |
![]() |
![]() |
![]() |
![]() |
vertex- and edge-transitive | edge-transitive and regular | edge-transitive | ||
![]() |
![]() |
|||
![]() |
![]() |
![]() |
||
vertex-transitive | regular | |||
![]() |
||||
![]() |
||||
Cayley graph |
Hello,
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)
The result of the move request was: consensus not to move the page as proposed at this time, per the discussion below. Thanks to all for their participation in the discussion. Dekimasu よ! 01:42, 20 April 2018 (UTC)
Symmetric graph →
Arc-transitive graph – This type of graph is usually called an
arc-transitive graph. A
symmetric graph can also be a graph that is both
vertex-transitive and
edge-transitive. The article also mentions
t-arc-transitive graphs, which are never called
t-symmetric graphs. Therefore, this page should be moved to
arc-transitive graph.
Math Maniac (
talk) 15:32, 8 April 2018 (UTC)--Relisting.
Dekimasu
よ!
18:21, 15 April 2018 (UTC)
I know that this discussion is finished, but I would like to point out that Maproom was wrong. The Holt graph is not arc-transitive by any definition. It is a graph that is vertex-transitive and edge-transitive, but not arc-transitive. By a common definition of symmetric graph, the Holt graph is symmetric. The fact that symmetric graph and arc-transitive graph have different meanings is the reason that this page should be moved. Math Maniac ( talk) 19:08, 28 July 2018 (UTC)
I just read the definition of a symmetric graph in the book Topics in Algebraic Graph Theory (Beineke and Wilson, eds., 2007).
That definition differs from the one in this article, because the book's definition requires not only that the automorphism group of a graph be transitive on edges, but also that it be transitive on vertices.
Are both definitions used currently by researchers? If so, the article should mention this fact.
Or is one of these definitions wrong?
Of course, for a graph G, IF for any two distinct vertices v and w ∊ G, both of [v,w] and [w,v] are always considered to be edges of G ... then transitivity on vertices would follow from transitivity on edges. 2601:200:C000:1A0:F8A4:C598:11E7:9879 ( talk) 17:56, 21 June 2022 (UTC)