Hamiltonian Walk

A Hamiltonian walk on a connected graph is a closed walk of minimal length which visits every vertex of a graph (and may visit vertices and edges multiple times). For example, a Hamiltonian walk on the above 3-pan graph is given by the vertex sequence 4, 3, 1, 2, 3, 4 and hence is of length 5.

The length of a Hamiltonian walk in a graph  is called the Hamiltonian number . A Hamiltonian graph has , where  is the vertex count. A graph with  is said to be almost Hamiltonian.

---

REFERENCES

Asano, T.; Nishizeki, T.; and Watanabe, T. "An Upper Bound on the Length of a Hamiltonian Walk of a Maximal Planar Graph." J. Graph Th. 4, 315-336, 1980.

Asano, T.; Nishizeki, T.; and Watanabe, T. "An Approximation Algorithm for the Hamiltonian Walk Problem on Maximal Planar Graph." J. Discr. Appl. Math. 5, 211-222, 1983.

Bermond, J. C. "On Hamiltonian Walks." Congr. Numer. 15, 41-51, 1976.

Chartrand, G.; Thomas, T.; Saenpholphat, V.; and Zhang, P. "A New Look at Hamiltonian Walks." Bull. Inst. Combin. Appl. 42, 37-52, 2004.

Goodman, S. E. and Hedetniemi, S. T. "On Hamiltonian Walks in Graphs." In Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing. Held at Florida Atlantic University, Boca Raton, Fla., March 5-8, 1973 (Ed. F. Hoffman, R. B. Levow, and R. S. D. Thomas). Winnipeg, Manitoba: Utilitas Mathematica, pp. 335-342, 1973.

Goodman, S. E. and Hedetniemi, S. T. "On Hamiltonian Walks in Graphs." SIAM J. Comput. 3, 214-221, 1974.

Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.

Takamizawa, K.; Nishizeki, T.; and Saito, N. "An Algorithm for Finding a Short Closed Spanning Walk in a Graph." Networks 10, 249-263, 1980.Vacek, P. "On Open Hamiltonian Walks in Graphs." Arch. Math. (Brno) 27A, 105-111, 1991.

اخر الاخبار

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

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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