TOPICS
Search

Apex-Selector Graphs


ApexSelectorGraphs

The apex-selector graphs are the four 16-vertex, 24-edge cubic Hamiltonian graphs called Firstapex, Secondapex, Thirdapex, and Fourthapex by Robertson et al. (2019). Each has girth 5, graph diameter 4, and chromatic number 3. All four are apex and contain the drum graph as a topological minor.

Robertson et al. (2019) do not explain the term "apex-selector", which appears to refer to the collective role of the four graphs in the apex characterizations below. The words first, second, third, and fourth are ordinal labels.

A cubic graph is cyclically 5-connected if it has girth at least 5 and every edge cut separating two subgraphs that contain cycles has at least five edges. It is dodecahedrally-connected if no 5-edge cut having at least seven vertices on each side cuts off a subgraph that can be drawn in a disk with its five attachment vertices on the boundary.

A graph is arched if deleting one graph edge makes it planar, and is doubly-apex if identifying two of its vertices makes it planar. The characterization involving the apex-selectors states that a dodecahedrally-connected graph is either arched or doubly-apex if and only if it contains neither the Petersen graph nor any apex-selector as a topological minor (Robertson et al. 2019).

The four apex-selector graphs are implemented in the Wolfram Language as GraphData["FirstapexGraph"], GraphData["SecondapexGraph"], GraphData["ThirdapexGraph"], and GraphData["FourthapexGraph"].


See also

Apex Graph, Drum Graph, Petersen Graph, Sailboat Graph

Explore with Wolfram|Alpha

References

House of Graphs. Apex-Selector Graphs. Firstapex Graph, Secondapex Graph, and Thirdapex Graph.Robertson, N.; Seymour, P. D.; and Thomas, R. "Excluded Minors in Cubic Graphs." J. Combin. Th., Ser. B 138, 219-285, 2019. https://doi.org/10.1016/j.jctb.2019.02.002.

Cite this as:

Weisstein, Eric W. "Apex-Selector Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Apex-SelectorGraphs.html

Subject classifications