McGee graph

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. 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, the graph is named after McGee who published the result in 1960¹. Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966. 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 , also known as the Nauru graph. 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. The graph is 1-planar.

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. 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, the graph is named after McGee who published the result in 1960. Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966. 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 , also known as the Nauru graph. 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. The graph is 1-planar. ==Algebraic properties== The characteristic polynomial of the McGee graph is x^3(x-3)(x-2)^3(x+1)^2(x+2)(x^2+x-4)(x^3+x^2-4x-2)^4 . 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. The automorphism group of the McGee graph, meaning its group of symmetries, has 32 elements. This group is isomorphic to the group of all affine transformations of \mathbb{Z}/8\mathbb{Z} , i.e., transformations of the form x \mapsto ax + b where a,b \in \mathbb{Z}/8\mathbb{Z} and a is invertible, so a = 1, 3, 5, 7 . This is one of the two smallest possible group G with an outer automorphism that maps every element g \in G to an element conjugate to g . ==Gallery== Image:McGee graph crossing number.svg|The crossing number of the McGee graph is 8. Image:McGee graph 3COL.svg |The chromatic number of the McGee graph is 3. Image:McGee graph 3color edge.svg|The chromatic index of the McGee graph is 3. Image:Acyclic_coloring.svg|The acyclic chromatic number of the McGee graph is 3. Image:McGee graph.svg|Alternative drawing of the McGee graph.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1341665912 under CC BY-SA 4.0; modifications have been made.