Folkman graph

In the mathematical field of graph theory, the Folkman graph, named after Jon Folkman, is a bipartite 4-regular graph with 20 vertices and 40 edges.[1]

Folkman graph
The Folkman graph
Named afterJon Folkman
Vertices20
Edges40
Radius3
Diameter4
Girth4
Automorphisms3840
Chromatic number2
Chromatic index4
Book thickness3
Queue number2
PropertiesHamiltonian
Regular
Bipartite
Semi-symmetric
Eulerian
Perfect
Table of graphs and parameters

The Folkman graph is Hamiltonian and has chromatic number 2, chromatic index 4, radius 3, diameter 4 and girth 4. It is also a 4-vertex-connected and 4-edge-connected perfect graph. It has book thickness 3 and queue number 2.[2]

Algebraic properties

The automorphism group of the Folkman graph acts transitively on its edges but not on its vertices. It is the smallest undirected graph that is edge-transitive and regular, but not vertex-transitive.[3] Such graphs are called semi-symmetric graphs and were first studied by Folkman in 1967 who discovered the graph on 20 vertices that now is named after him.[4]

As a semi-symmetric graph, the Folkman graph is bipartite, and its automorphism group acts transitively on each of the two vertex sets of the bipartition. In the diagram below indicating the chromatic number of the graph, the green vertices can not be mapped to red ones by any automorphism, but any red vertex can be mapped on any other red vertex and any green vertex can be mapped on any other green vertex.

The characteristic polynomial of the Folkman graph is .

References
  1. Weisstein, Eric W. "Folkman graph". MathWorld.
  2. Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  3. Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 186-187, 1990
  4. Folkman, J. (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory, 3 (3): 215–232, doi:10.1016/S0021-9800(67)80069-3
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.