Folkman graph
Encyclopedia
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.
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
.
and regular, but not vertex-transitive
. Such graphs are called semi-symmetric graph
s and were first studied by Folkman in 1967 who discovered the graph on 20 vertices that now is named after him.
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
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Folkman graph, named after Jon Folkman
Jon Folkman
Jon Hal Folkman was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.-Schooling:Folkman was a Putnam Fellow in 1960. He received his Ph.D...
, is a bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
4-regular
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
graph with 20 vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
and 40 edges.
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
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
and 4-edge-connected
K-edge-connected graph
In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G = be an arbitrary graph....
perfect graph
Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
.
Algebraic properties
The automorphism group of the Folkman graph graph acts transitively on its edges but not on its vertices. It is the smallest undirected graph that is edge-transitiveEdge-transitive graph
In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....
and regular, but not vertex-transitive
Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
. Such graphs are called semi-symmetric graph
Semi-symmetric graph
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....
s and were first studied by Folkman in 1967 who discovered the graph on 20 vertices that now is named after him.
As a semi-symmetric graph, the Folkman graph is bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
, 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
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
of the Folkman graph is
.