Semi-symmetric graph

Semi-symmetric graph

In mathematics, 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. A semi-symmetric graph must be bipartite, and its automorphism group must act transitively on each of the two vertex sets of the bipartition.

Semi-symmetric graphs were first studied by harvtxt|Folkman|1967, who discovered the smallest semi-symmetric graph, the Folkman graph on 20 vertices. The smallest cubic semi-symmetric graph is the Gray graph on 54 vertices. [The Gray graph was first observed to be semi-symmetric by harvtxt|Bouwer|1968. It was proven to be the smallest cubic semi-symmetric graph by Dragan Marušič and Aleksander Malnič.] A complete list of cubic semi-symmetric graphs on at most 768 vertices is given by harvtxt|Conder|Malnič|Marušič|Potočnik|2006.

Notes

References

*citation
last = Bouwer | first = I. Z.
title = An edge but not vertex transitive cubic graph
journal = Bulletin of the Canadian Mathematical Society
volume = 11 | pages = 533–535 | year = 1968.

*citation
last1 = Conder | first1 = Marston
last2 = Malnič | first2 = Aleksander
last3 = Marušič | first3 = Dragan | authorlink3 = Dragan Marušič
last4 = Potočnik | first4 = Primož
title = A census of semisymmetric cubic graphs on up to 768 vertices
journal = Journal of Algebraic Combinatorics
volume = 23 | year = 2006 | pages = 255–294
doi = 10.1007/s10801-006-7397-3.

*citation
first = J. | last = Folkman
title = Regular line-symmetric graphs
journal = Journal of Combinatorial Theory
volume =3 | year = 1967 | pages = 215–232.

External links

*mathworld | urlname = SemisymmetricGraph | title = Semisymmetric Graph


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Graph automorphism — In graph theoretical mathematics, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge vertex connectivity.Formally, an automorphism of a graph G = ( V , E ) is a permutation sigma;… …   Wikipedia

  • Gray graph — infobox graph name = Gray graph image caption = namesake = Marion Cameron Gray vertices = 54 edges = 81 girth = 8 chromatic number = 2 chromatic index = 3 properties = Cubic Semi symmetricIn mathematics, the Gray graph is an undirected bipartite… …   Wikipedia

  • Vertex-transitive graph — In mathematics, a vertex transitive graph is a graph G such that, given any two vertices v1 and v2 of G , there is some automorphism : f : V(G) → V(G) such that : f (v1) = v2. In other words, a graph is vertex transitive if its automorphism group …   Wikipedia

  • Cubic graph — Not to be confused with graphs of cubic functions. The Petersen graph is a Cubic graph …   Wikipedia

  • Edge-transitive graph — In mathematics, an edge transitive graph is a graph G such that, given any two edges e 1 and e 2 of G , there is an automorphism of G that maps e 1 to e 2.In other words, a graph is edge transitive if its automorphism group acts transitively upon …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Dragan Marušič — (born 1953) is a Slovene mathematician. His research focuses on topics in algebraic graph theory, particularly the symmetry of graphs and the action of finite groups on combinatorial objects. In 2002, he helped show that the Gray graph is the… …   Wikipedia

  • Continuous-time quantum walk — A Continuous time quantum walk (CTQW) is a walk on a given connected graph that is dictated by a time varying unitary matrix that relies on the Hamiltonian of the quantum system and the adjacency matrix. CTQW belongs to what is known as Quantum… …   Wikipedia

  • Graphe symétrique — Le Graphe de Petersen est un graphe cubique symétrique. En théorie des graphes un graphe G est symétrique (ou arc transitif) si, étant donné deux paires de sommets reliés par une arête u1 v1 et u2 v2 de G, il existe un automorphisme de… …   Wikipédia en Français

  • Dynkin diagram — See also: Coxeter–Dynkin diagram Finite Dynkin diagrams Affine (extended) Dynkin diagrams …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”