In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a
graph is symmetric (or arc-transitive) if, given any two pairs of adjacent
vertices and of , there is an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphis ...
:
such that
:
and
In other words, a graph is symmetric if its
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
acts
transitively on
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
s of adjacent vertices (that is, upon edges considered as having a direction).
Such a graph is sometimes also called -transitive
or flag-transitive.
By definition (ignoring and ), a symmetric graph without
isolated vertices must also be
vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of fa ...
.
Since the definition above maps one edge to another, a symmetric graph must also be
edge-transitive
In geometry, a polytope (for example, a polygon or a polyhedron) or a tiling is isotoxal () or edge-transitive if its symmetries act transitively on its edges. Informally, this means that there is only one type of edge to the object: given t ...
. However, an edge-transitive graph need not be symmetric, since might map to , but not to .
Star graphs
A star is an astronomical object comprising a luminous spheroid of plasma held together by its gravity. The nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night, but their immense distances from Earth ...
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
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
degree.
However, for
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
**Even language, a language spoken by the Evens
* Odd and Even, a solitaire game wh ...
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
In graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such graphs are not common. It is named after Peter ...
, 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 is defined to be a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A graph is a graph such that the automorphism group acts transitively on , but not on . Since are simply edges, every symmetric graph of degree 3 or more must be for some , and the value of can be used to further classify symmetric graphs. The cube is , for example.
Examples
Two basic families of symmetric graphs for any number of vertices are the
cycle graphs (of degree 2) and the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
s. Further symmetric graphs are formed by the vertices and edges of the regular and quasiregular polyhedra: the
cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the only ...
,
octahedron
In geometry, an octahedron (plural: octahedra, octahedrons) is a polyhedron with eight faces. The term is most commonly used to refer to the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at ea ...
,
icosahedron
In geometry, an icosahedron ( or ) is a polyhedron with 20 faces. The name comes and . The plural can be either "icosahedra" () or "icosahedrons".
There are infinitely many non- similar shapes of icosahedra, some of them being more symmetrica ...
,
dodecahedron,
cuboctahedron, and
icosidodecahedron
In geometry, an icosidodecahedron is a polyhedron with twenty (''icosi'') triangular faces and twelve (''dodeca'') pentagonal faces. An icosidodecahedron has 30 identical vertices, with two triangles and two pentagons meeting at each, and 60 i ...
. Extension of the cube to n dimensions gives the hypercube graphs (with 2
n vertices and degree n). Similarly extension of the octahedron to n dimensions gives the graphs of the
cross-polytope
In geometry, a cross-polytope, hyperoctahedron, orthoplex, or cocube is a regular, convex polytope that exists in ''n''- dimensional Euclidean space. A 2-dimensional cross-polytope is a square, a 3-dimensional cross-polytope is a regular octahe ...
s, this family of graphs (with 2n vertices and degree 2n-2) are sometimes referred to as the
cocktail party graphs - they are complete graphs with a set of edges making a perfect matching removed. Additional families of symmetric graphs with an even number of vertices 2n, are the evenly split
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
s K
n,n and the
crown graph
In graph theory, a branch of mathematics, a crown graph on vertices is an undirected graph with two sets of vertices and and with an edge from to whenever .
The crown graph can be viewed as a complete bipartite graph from which the edges ...
s on 2n vertices. Many other symmetric graphs can be classified as
circulant graph
In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings.
Equivalent definitions
Cir ...
s (but not all).
The
Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree
Cubic Symmetric graphs
Combining the symmetry condition with the restriction that graphs be
cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. They all have an even number of vertices. The Foster census and its extensions provide such lists. The Foster census was begun in the 1930s by
Ronald M. Foster while he was employed by
Bell Labs
Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984),
then AT&T Bell Laboratories (1984–1996)
and Bell Labs Innovations (1996–2007),
is an American industrial research and scientific development company owned by mul ...
, and in 1988 (when Foster was 92
) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form. The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices
[Biggs, p. 148][Weisstein, Eric W.,]
Cubic Symmetric Graph
, from Wolfram MathWorld. (ten of these are also
distance-transitive; the exceptions are as indicated):
Other well known cubic symmetric graphs are the
Dyck graph
In the mathematical field of graph theory, the Dyck graph is a 3- regular graph with 32 vertices and 48 edges, named after Walther von Dyck.
It is Hamiltonian with 120 distinct Hamiltonian cycles. It has chromatic number 2, chromatic index 3, r ...
, the
Foster graph and the
Biggs–Smith graph. The ten distance-transitive graphs listed above, together with the
Foster graph and the
Biggs–Smith graph, are the only cubic distance-transitive graphs.
Properties
The
vertex-connectivity of a symmetric graph is always equal to the
degree ''d''.
In contrast, for
vertex-transitive graphs in general, the vertex-connectivity is bounded below by 2(''d'' + 1)/3.
A ''t''-transitive graph of degree 3 or more has
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
at least 2(''t'' – 1). However, there are no finite ''t''-transitive graphs of degree 3 or more for ''t'' ≥ 8. In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for ''t'' ≥ 6.
See also
*
Algebraic graph theory
*
Gallery of named graphs
Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minim ...
*
Regular map
References
{{reflist
External links
Cubic symmetric graphs (The Foster Census) Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
Trivalent (cubic) symmetric graphs on up to 10000 vertices Marston Conder
Marston Donald Edward Conder (born 9 September 1955) is a New Zealand mathematician, a Distinguished Professor of Mathematics at Auckland University, , 2011.
Algebraic graph theory
Graph families
Regular graphs