Almost Hamiltonian Graph

There are several definitions of "almost Hamiltonian" in use.

As defined by Punnim et al. (2007), an almost Hamiltonian graph is a graph on  nodes having Hamiltonian number .

As defined by Sanders (1987), a graph  with  vertices is almost Hamiltonian if every subset of  vertices is contained in a circuit, a definition which is similar to that for a maximally nonhamiltonian graph.

This work adopts the definition of Punnim et al. (2007). The numbers of almost Hamiltonian graphs of this type on , 2, ... vertices are 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS A185360), the first few of which are illustrated above.

Since a tree has Hamiltonian number , an almost Hamiltonian tree satisfies , giving . Since the 3-path graph  is the only tree on three nodes, it is also the only almost Hamiltonian tree.

Hypohamiltonian graphs are almost Hamiltonian. Many (or perhaps even all?) snarks are almost Hamiltonian.

Punnim et al. (2007) showed that the generalized Petersen graph  is almost Hamiltonian iff  and .

Punnim et al. (2007) proved that there exists an almost Hamiltonian cubic graph for every even order . The Petersen graph is the unique almost Hamiltonian cubic graph on 10 vertices, and Tietze's graph is the unique almost Hamiltonian cubic graph on 12 vertices (Punnim et al. 2007). Punnim et al. (2007) proved that a cubic nonhamiltonian graph on  vertices is almost Hamiltonian iff it is 2-connected and contains a cycle of length . Examples of 2-connected cubic nonhamiltonian graphs on  vertices lacking a -cycle and therefore not almost Hamiltonian are summarized in the following table.

	graph
14	14-cubic graph 120
30	triangle-replaced Petersen graph
36	36-Zamfirescu graph
50	Georges graph
56	56-Ellingham-Horton graph

---

 

REFERENCES

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

Sanders, J. H. "Circuit Preserving Edge Maps II." J. Combin. Th., Ser. B 42, 146-155, 1987.

Sloane, N. J. A. Sequence A185360 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

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

قسم الشؤون الفكرية يطلق مسابقة النور الزكي الرمضانية في ذي قار

المجمَع العلمي يقيم المجلس القرآنيّ التعليميّ الخاص بطلبة الحفظ

قرّاء من لبنان وإيران والفلبين يشاركون في الحلقة السابعة من جائزة العميد القرآنية بنسختها الثالثة

قسم العلاقات يقيم أمسية رمضانية ثقافية لطلبة الأقسام الداخلية في جامعة كربلاء

المزيد

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

دراسة تحذر من الإفراط في ممارسة الرياضة.. كيف يضر دماءك؟

الطهي بزيت الزيتون.. مضر أم مفيد؟

دماغ الرضع في خطر.. دراسة تحذر من "العدو الخفي"

التمر بالحليب عند الإفطار.. "كنز صحي" في رمضان

المزيد

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

أثر نفسي غير متوقع للرياضة.. مرتبط بالغضب

القمر يواصل الانكماش.. رصد تشققات حديثة على سطحه

إطلاق أول تطبيق مراسلة "مشفّر".. ثورة في عالم الدردشة

خلل تقني يؤجّل أول رحلة مأهولة إلى القمر منذ عقود

المزيد

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

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