H^*-Connected Graph

A graph is said to be -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 -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 -connected except cycle graphs  for  and the dodecahedral graph." It was been verified up to  nodes.

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength