Metraipolis › archive › dc_ab68f10339ac

Symmetric graph — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Symmetric_graph
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T18:48:28.778Z
SHA-256 of the archived text
c3b947efc5e6c74864aa5609c92cfc8c69e25d1d4d4681dcb55a063059ce3138
Stable URL of this page
https://metraipolis.com/documento/dc_ab68f10339ac

How to cite

Symmetric graph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Symmetric_graph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ab68f10339ac (Metraipolis archive dc_ab68f10339ac, sha256 c3b947efc5e6c74864aa5609c92cfc8c69e25d1d4d4681dcb55a063059ce3138)
BibTeX
@misc{dcab68f10339ac,
  title = {Symmetric graph — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Symmetric_graph},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ab68f10339ac; sha256 c3b947efc5e6c74864aa5609c92cfc8c69e25d1d4d4681dcb55a063059ce3138},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Symmetric_graph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the mathematical field of graph theory, a graph G is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices ( u 1 , v 1 ) {\displaystyle (u_{1},v_{1})} and ( u 2 , v 2 ) {\displaystyle (u_{2},v_{2})} of G, there is an automorphism f : V ( G ) → V ( G ) {\displaystyle f:V(G)\rightarrow V(G)} such that f ( u 1 ) = u 2 {\displaystyle f(u_{1})=u_{2}} and f ( v 1 ) = v 2 . {\displaystyle f(v_{1})=v_{2}.} In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive. By definition (ignoring u1 and u2), a symmetric graph without isolated vertices must also be vertex-transitive. Since the definition above maps one edge to another, a symmetric graph must also be edge-transitive. However, an edge-transitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Star graphs are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example, semi-symmetric graphs are edge-transitive and regular, but not vertex-transitive. Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree. However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric. Such graphs are called half-transitive. The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices. Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above. A distance-transitive graph is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition. A t-arc is defined to be a sequence of t + 1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A t-transitive graph is a graph such that the automorphism group acts transitively on t-arcs, but not on (t + 1)-arcs. Since 1-arcs are simply edges, every symmetric graph of degree 3 or more must be t-transitive for some t, and the value of t can be used to further classify symmetric graphs. The cube is 2-transitive, for example. Note that conventionally the term "symmetric graph" is not complementary to the term "asymmetric graph," as the latter refers to a graph that has no nontrivial symmetries at all.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Symmetric graph» — https://en.wikipedia.org/wiki/Symmetric_graph
Wikidata Q1205074 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1205074
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Symmetric_graph?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1317719951, consultata il 2026-10-15T18:09:34.182Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 02d623f5baa95e298fbe8bef21cbd5734226e08420ad9e1b7953305912a41e50