Semi-symmetric graph

From Wikipedia, the free encyclopedia

The Folkman graph, the smallest semi-symmetric graph.

Graph families defined by their automorphisms
distance-transitive	$\rightarrow$	distance-regular	$\leftarrow$	strongly regular
$\downarrow$
symmetric (arc-transitive)	$\leftarrow$	t-transitive, t ≥ 2
$\downarrow$ _{(if connected)}
vertex- and edge-transitive	$\rightarrow$	edge-transitive and regular	$\rightarrow$	edge-transitive
$\downarrow$		$\downarrow$		$\downarrow$
vertex-transitive	$\rightarrow$	regular	$\rightarrow$	_{(if bipartite)} biregular
$\uparrow$
Cayley graph		skew-symmetric		asymmetric

In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of incident edges, and there is a symmetry taking any of its edges to any other of its edges, but there is some pair of vertices that cannot be mapped into each other by a symmetry.

Properties

A semi-symmetric graph must be bipartite, and its automorphism group must act transitively on each of the two vertex sets of the bipartition. In the diagram on the right, green vertices can not be mapped to red ones by any automorphism.

History

Semi-symmetric graphs were first studied E. Dauber, a student of F. Harary, in a paper, no longer available, titled "On line- but not point-symmetric graphs". This was seen by Jon Folkman, whose paper, published in 1967, includes the smallest semi-symmetric graph, now known as the Folkman graph, on 20 vertices.^[1]

Cubic graphs

The smallest cubic semi-symmetric graph (that is, one in which each vertex is incident to exactly three edges) is the Gray graph on 54 vertices. It was first observed to be semi-symmetric by Bouwer (1968). It was proven to be the smallest cubic semi-symmetric graph by Dragan Marušič and Aleksander Malnič.^[2]

All the cubic semi-symmetric graphs on up to 768 vertices are known. According to Conder, Malnič, Marušič and Potočnik, the four smallest possible cubic semi-symmetric graphs after the Gray graph are the Iofinova–Ivanov graph on 110 vertices, the Ljubljana graph on 112 vertices,^[3] a graph on 120 vertices with girth 8 and the Tutte 12-cage.^[4]

References

↑ Folkman, J. (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3 .
↑ Bouwer, I. Z. (1968), "An edge but not vertex transitive cubic graph", Bulletin of the Canadian Mathematical Society 11: 533–535, doi:10.4153/CMB-1968-063-0 .
↑ Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002), "The Ljubljana Graph", IMFM Preprints (Ljubljana: Institute of Mathematics, Physics and Mechanics) 40 (845) .
↑ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics 23 (3): 255–294, doi:10.1007/s10801-006-7397-3 .

External links

Weisstein, Eric W., "Semisymmetric Graph", MathWorld.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.