TOPICS
Search

H^*-Connected Graph


A graph is said to be H^*-connected if it is either Hamilton-connected or Hamilton-laceable.

S. Wagon (pers. comm., May. 20, 2013; Dupuis and Wagon 2014) conjecture that all connected vertex-transitive graphs are H^*-connected with the following exceptions: cycle graphs, the dodecahedral graph, Petersen graph, Coxeter graph, triangle-replaced Petersen graph, and triangle-replaced Coxeter graph. The conjecture can be restated as, "Every Hamiltonian vertex-transitive graph is H^*-connected except cycle graphs C_n for n>=5 and the dodecahedral graph." It was been verified up to n=31 nodes.


See also

Hamilton-Connected Graph, Hamilton-Laceable Graph, Nonhamiltonian Vertex-Transitive Graph, Triangle-Replaced Graph

Explore with Wolfram|Alpha

References

Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014. http://arxiv.org/abs/1408.5211.Dupuis, M. and Wagon, S. "Laceable Knights." To appear in Ars Math Contemp.

Cite this as:

Weisstein, Eric W. "H^*-Connected Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/H-Star-ConnectedGraph.html

Subject classifications