Hamilton-Connected Graph

 

A graph  is Hamilton-connected if every two vertices of  are connected by a Hamiltonian path (Bondy and Murty 1976, p. 61). In other words, a graph is Hamilton-connected if it has a  Hamiltonian path for all pairs of vertices  and . The illustration above shows a set of Hamiltonian paths that make the wheel graph  hamilton-connected.

By definition, a graph with vertex count  having a detour matrix whose off-diagonal elements are all equal to  is Hamilton-connected. Conversely, any graph having a detour matrix with an off-diagonal element less than  is not Hamilton-connected.

All Hamilton-connected graphs are Hamiltonian. All complete graphs are Hamilton-connected (with the trivial exception of the singleton graph), and all bipartite graphs are not Hamilton-connected.

Dupuis and Wagon (2014) conjectured that all non-bipartite Hamiltonian vertex-transitive graphs are Hamilton-connected except for odd cycle graphs  with  and the dodecahedral graph.

A simple algorithm for determining if a graph is Hamilton-connected proceeds as follows. For all pairs  of vertices:

1. Add a new vertex .

2. Add new edges  and .

3. If this graph is not Hamiltonian, return false; otherwise, continue to next pair.

If the algorithm checks all pairs without returning false, return true.

A small modification of a theorem due to Chvátal and Erdős establishes that if  for a graph , where  is the independence number and  the vertex connectivity, then  is Hamilton-connected (A. E. Brouwer, pers. comm., Dec. 17, 2012).

As a result of the theorem that for a connected regular graph  on  vertices with vertex degree  and smallest graph eigenvalue ,

it therefore follows that if

for a connected regular graph, the graph is Hamilton-connected (A. E. Brouwer, pers. comm., Dec. 17, 2012).

Every 8-connected claw-free graph is Hamilton-connected (Hu et al. 2005), as is every Johnson graph (Alspach 2013). Chen and Quimpo (1981) proved that a connected Cayley graph on a finite Abelian group of odd order with vertex degree at least three is Hamilton-connected.

Pensaert (2002) conjectured that for  with , the generalized Petersen graph  is Hamilton-laceable if  is even and  is odd, and Hamilton-connected otherwise.

The numbers of Hamilton-connected simple graphs on , 2, ... nodes are 1, 1, 1, 1, 3, 13, 116, ... (OEIS A057865), the first few of which are illustrated above.

Examples of Hamilton-connected graphs include antiprism graphs, complete graphs, Möbius ladders, prism graphs of odd order, wheel graphs, the truncated prism graph, truncated cubical graph, truncated tetrahedral graph, Grötzsch graph, Frucht graph, and Hoffman-Singleton graph.

---

REFERENCES

Alspach, B. "Johnson Graphs are Hamilton-Connected." Ars Math. Contemporanea 6, 21-23, 2013.

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 61, 1976.

Chen, C. C. and Quimpo, N. F. "On Strongly Hamiltonian Abelian Group Graphs." In Combinatorial Mathematics. VIII. Proceedings of the Eighth Australian Conference held at Deakin University, Geelong, August 25-29, 1980 

(Ed. K. L. McAvaney). Berlin: Springer-Verlag, pp. 23-34, 1981.

Dupuis, M. and Wagon, S. "Laceable Knights." To appear in Ars Math Contemp.Hu, Z.; Tian, F.; and Wei, B. "Hamilton Connectivity of Line Graphs and Claw-Free Graphs." J. Graph Th. 50, 130-141, 2005.

Pensaert, W. P. J. "Hamilton Paths in Generalized Petersen Graphs." Thesis. Waterloo, Ontario, Canada. January 2002.

 http://etd.uwaterloo.ca/etd/wpjpensaert2002.pdf.Sloane, N. J. A. Sequence A057865 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

اخبار العتبة العباسية المقدسة

تكريم الجامعات الفائزة ولجنة التحكيم المشاركة في مسابقة النور القرآنية الدولية الجامعية

اختتام فعاليات مسابقة النور القرآنية الدولية الجامعية في جامعة العميد

قسم الصيانة يُنهي تنصيب منظومة الإنذار المبكّر للحرائق في ثانوية نور العباس (عليه السلام) للبنين

في يومها الثاني.. مسابقة النور القرآنية تواصل فعالياتها في جامعة العميد

المزيد

الآخبار الصحية

أول إرشادات غذائية قائمة على الأدلة لمعالجة الإمساك المزمن

صباح بلا إفطار؟.. صحتك في خطر!

هل يمكن للجلد أن يكشف عن صحتك العقلية؟.. دراسة حديثة تجيب

السر في مطبخك.. 6 أطعمة تمنح عظامك قوة الشباب

المزيد

الآخبار التكنلوجية

ناسا تكشف: كوكب الأرض أصبح أقل لمعانا خلال العقود الماضية

دراسة: الوقت الذي تستخدم فيه هاتفك قد يفضح حالتك النفسية

الهنغاري لاسلو كراسناهوركاي يفوز بجائزة نوبل للآداب 2025

رسميا.. إعلان الفائز بجائزة نوبل للسلام لعام 2025

المزيد

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

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