Barnette's Conjecture

Barnette's conjecture asserts that every 3-connected bipartite cubic planar graph is Hamiltonian. The only graph on nine or fewer vertices satisfying Barnette's conditions is the cubical graph, which is indeed Hamiltonian. The skeletons of the truncated octahedron, great rhombicuboctahedron, and great rhombicosidodecahedron also satisfy the conditions and, since they are Archimedean solids, are indeed Hamiltonian. Holton et al. (1985) proved that all graphs having fewer than 66 vertices satisfy the conjecture, but the general conjecture remains open.

Similarly, Barnette conjectured that all cubic, 3-connected, planar graphs with a face size of at most 6 are Hamiltonian. Aldred et al. (2000) have verified this conjecture for all graphs with fewer than 177 vertices.

---

REFERENCES

Aldred, R.; Bau, S.; Holton, D., and McKay, B. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.

Barnette, D. Conjecture 5 in Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968 (Ed. W. T. Tutte). New York: Academic Press, 1969.

Holton, D.; Manvel, B.; and McKay, B. "Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs." J. Combin. Th. Ser. B 38, 279-297, 1985.

Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc. Math. 44, 327-330, 1983.

اخر الاخبار

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

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

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

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

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

المزيد

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

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

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

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

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

المزيد

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

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

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

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

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

المزيد

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

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