26-fullerene graph
{{Short description|Polyhedral graph with 26 vertices and 39 edges}}
{{Infobox graph
| name= 26-fullerene
| image = Godsil-Royle (26-fullerene).png
| image_size= 250px
| image_caption = The 26-fullerene graph with its hexagons highlighted
| vertices = 26
| edges = 39
| properties = faces = 3 hexagons,
12 pentagons
| radius = 5
| diameter = 6
| girth = 5
| chromatic_number=3
| chromatic_index=3
}}
In the mathematical field of graph theory, the 26-fullerene graph is a polyhedral graph with V = 26 vertices and E = 39 edges. Its planar embedding has three hexagonal faces (including the one shown as the external face of the illustration) and twelve pentagonal faces. As a planar graph with only pentagonal and hexagonal faces, meeting in three faces per vertex, this graph is a fullerene. The existence of this fullerene has been known since at least 1968.{{citation
| last = Grünbaum | first = B. | author-link = Branko Grünbaum
| doi = 10.1007/BF02771220 | doi-access=free
| journal = Israel Journal of Mathematics
| mr = 0244854
| pages = 398–411 (1969)
| title = Some analogues of Eberhard's theorem on convex polytopes
| volume = 6
| year = 1968| issue = 4 }}. See line 19 of table, p. 411, completely characterizing which numbers of hexagons are possible in a fullerene.
Properties
The 26-fullerene graph has prismatic symmetry, the same group of symmetries as the triangular prism. This symmetry group has 12 elements; it has six symmetries that arbitrarily permute the three hexagonal faces of the graph and preserve the orientation of its planar embedding, and another six orientation-reversing symmetries.
The number of fullerenes with a given even number of vertices grows quickly in the number of vertices; 26 is the largest number of vertices for which the fullerene structure is unique. The only two smaller fullerenes are the graph of the regular dodecahedron (a fullerene with 20 vertices) and the graph of the truncated hexagonal trapezohedron (a 24-vertex fullerene),{{cite OEIS|A007894|mode=cs2}} which are the two types of cells in the Weaire–Phelan structure.
The 26-fullerene graph has many perfect matchings. One must remove at least five edges from the graph in order to obtain a subgraph that has exactly one perfect matching. This is a unique property of this graph among fullerenes in the sense that, for every other number of vertices of a fullerene, there exists at least one fullerene from which one can remove four edges to obtain a subgraph with a unique perfect matching.{{citation
| last1 = Yang | first1 = Qin
| last2 = Zhang | first2 = Heping
| last3 = Lin | first3 = Yuqing
| issue = 3
| journal = MATCH Communications in Mathematical and in Computer Chemistry
| mr = 3444683
| pages = 673–692
| title = On the anti-forcing number of fullerene graphs
| volume = 74
| year = 2015| arxiv = 1503.01900
}}
The vertices of the 26-fullerene graph can be labeled with sequences of 12 bits, in such a way that distance in the graph equals half of the Hamming distance between these bitvectors.
This can also be interpreted as an isometric embedding from the graph into a 12-dimensional taxicab geometry. The 26-fullerene graph is one of only five fullerenes with such an embedding.{{citation
| last = Marcusanu | first = Mihaela
| isbn = 978-1109-98335-7
| mr = 2710114
| publisher = Bowling Green State University
| series = Ph.D. thesis
| title = The classification of -embeddable fullerenes
| url = http://rave.ohiolink.edu/etdc/view?acc_num=bgsu1180115123
| year = 2007}}. For the embedding, see Figure 5.3, p. 52.
In popular culture
In 2009, The New York Times published a puzzle involving Hamiltonian paths in this graph, taking advantage of the correspondence between its 26 vertices and the 26 letters of the English alphabet.{{citation|url=https://tierneylab.blogs.nytimes.com/2009/05/04/the-hamiltonian-puzzle|title=The Hamiltonian Puzzle|newspaper=The New York Times|date=May 4, 2009|first=John|last=Tierney|author-link=John Tierney (journalist)}}{{citation|url=http://www.mathematica-journal.com/issue/v11i3/contents/superhamilton/superhamilton.pdf|title=The Icosian game, revisited|last=Pegg|first=Ed Jr.|author-link=Ed Pegg Jr.|journal=The Mathematica Journal|volume=11|issue=3|year=2009|pages=310–314|doi=10.3888/tmj.11.3-1 }}