McGee graph | |
---|---|
![]() The McGee graph | |
Named after | W. F. McGee |
Vertices | 24 |
Edges | 36 |
Radius | 4 |
Diameter | 4 [1] |
Girth | 7 [1] |
Automorphisms | 32 [1] |
Chromatic number | 3 [1] |
Chromatic index | 3 [1] |
Book thickness | 3 |
Queue number | 2 |
Properties |
Cubic Cage Hamiltonian |
Table of graphs and parameters |
In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3- regular graph with 24 vertices and 36 edges. [1]
The McGee graph is the unique (3,7)- cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage that is not a Moore graph.
First discovered by Sachs but unpublished, [2] the graph is named after McGee who published the result in 1960. [3] Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966. [4] [5] [6]
The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the generalized Petersen graph G(12,5), also known as the Nauru graph. [7] [8]
The McGee graph has radius 4, diameter 4, chromatic number 3 and chromatic index 3. It is also a 3- vertex-connected and a 3- edge-connected graph. It has book thickness 3 and queue number 2. [9]
The characteristic polynomial of the McGee graph is
The automorphism group of the McGee graph is of order 32 and doesn't act transitively upon its vertices: there are two vertex orbits, of lengths 8 and 16. The McGee graph is the smallest cubic cage that is not a vertex-transitive graph. [10]
McGee graph | |
---|---|
![]() The McGee graph | |
Named after | W. F. McGee |
Vertices | 24 |
Edges | 36 |
Radius | 4 |
Diameter | 4 [1] |
Girth | 7 [1] |
Automorphisms | 32 [1] |
Chromatic number | 3 [1] |
Chromatic index | 3 [1] |
Book thickness | 3 |
Queue number | 2 |
Properties |
Cubic Cage Hamiltonian |
Table of graphs and parameters |
In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3- regular graph with 24 vertices and 36 edges. [1]
The McGee graph is the unique (3,7)- cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage that is not a Moore graph.
First discovered by Sachs but unpublished, [2] the graph is named after McGee who published the result in 1960. [3] Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966. [4] [5] [6]
The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the generalized Petersen graph G(12,5), also known as the Nauru graph. [7] [8]
The McGee graph has radius 4, diameter 4, chromatic number 3 and chromatic index 3. It is also a 3- vertex-connected and a 3- edge-connected graph. It has book thickness 3 and queue number 2. [9]
The characteristic polynomial of the McGee graph is
The automorphism group of the McGee graph is of order 32 and doesn't act transitively upon its vertices: there are two vertex orbits, of lengths 8 and 16. The McGee graph is the smallest cubic cage that is not a vertex-transitive graph. [10]