McGee graph

McGee graph
McGee Graph
McGee graph hamiltonian.svg
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]
Properties Cubic
Cage
Hamiltonian
v · 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 McGeeGraph 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 the proven the unique (3,7)-cage by Tutte in 1966.[4][5][6]

The smallest cubic graphs with crossing numbers 1–8 are known (sequence A110507 in OEIS). The smallest 8-crossing graph is the McGee graph. There exists 5 non-isomorphic cubic graphs of order 24 with crossing number 8.[7] One of them is the generalized Petersen graph G(12,5), also known as the Nauru graph.[8]

The McGeeGraph 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.

Algebraic properties

The characteristic polynomial of the McGeeGraph graph is : x3(x − 3)(x − 2)3(x + 1)2(x + 2)(x2 + x − 4)(x3 + x2 − 4x − 2)4.

The automorphism group of the McGee graph is of order 32 and doesn't acts transitively upon its vertices: there are two vertex orbits of lengths 8 and 16. The McGee is the smallest cubic cage that is not a vertex-transitive graph.[9]

Gallery

  • The crossing number of the McGee graph is 8.

  • The chromatic number of the McGee graph is 3.

  • The chromatic index of the McGee graph is 3.

  • The acyclic chromatic number of the McGee graph is 3.

  • Alternative drawing of the McGee graph.

References

  1. ^ a b c d e f Weisstein, Eric W., "McGee Graph" from MathWorld.
  2. ^ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960
  3. ^ McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960
  4. ^ Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
  5. ^ Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982
  6. ^ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
  7. ^ Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
  8. ^ Weisstein, Eric W., "Graph Crossing Number" from MathWorld.
  9. ^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Grafo de McGee — El Grafo de McGee Nombre en honor a W. F. McGee Vértices 24 …   Wikipedia Español

  • Graphe de McGee — Représentation du graphe de McGee. Nombre de sommets 24 Nombre d arêtes 36 Distribution des degrés 3 régulier Rayon …   Wikipédia en Français

  • Girth (graph theory) — In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.[1] If the graph does not contain any cycles (i.e. it s an acyclic graph), its girth is defined to be infinity.[2] For example, a 4 cycle (square) has… …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • Nauru graph — The Nauru graph is Hamiltonian. Vertices 24 Edges 36 Radius 4 …   Wikipedia

  • LCF-Notation — Der Foster Graph: Bezeichnet man den obersten Knoten mit v0, dann ist 90, [17, 9,37, 37,9, 17], 15 eine zugehörige LCF Notation. In der Kombinatorik als Teilgebiet der diskreten Mathematik ist die Lederberg Coxeter Fruchte Notation (kurz LCF)… …   Deutsch Wikipedia

  • Economic Affairs — ▪ 2006 Introduction In 2005 rising U.S. deficits, tight monetary policies, and higher oil prices triggered by hurricane damage in the Gulf of Mexico were moderating influences on the world economy and on U.S. stock markets, but some other… …   Universalium

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • 2005 Texas Longhorn football team — NCAATeamFootballSeason Year=2005 Team=Texas Longhorns ImageSize=130 Conference=Big 12 Conference Division=South ShortConference=Big 12 CoachRank=1 APRank=1 Record=13 ndash;0 ConfRecord=9 ndash;0 HeadCoach=Mack Brown OffCoach= Greg Davis DefCoach …   Wikipedia

  • Down syndrome — Classification and external resources Boy with Down syndrome assembling a …   Wikipedia

Share the article and excerpts

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