Pósa's Conjecture

Dirac (1952) proved that if the minimum vertex degree  for a graph  on  nodes, then  contains a Hamiltonian cycle (Bollobás 1978, Komlós et al. 1996).

In 1962, Pósa conjectured that  contains a square of a Hamiltonian cycle if  (Erdős 1964, p. 159; Komlós et al. 1996), where a graph  contains the square of a Hamiltonian cycle if there is a Hamiltonian cycle  such that , for , 2, ..., .

Komlós et al. (1996) proved that there exists a natural number  such that if a graph  has order  and minimum vertex degree at least , then  contains the square of a Hamiltonian cycle. This proved Pósa's conjecture (Erdős 1964) for sufficiently large . Kierstead and Quintana (1998) proved Pósa's conjecture for graphs  containing a 4-clique .

The conjecture was generalized by Seymour (1974) to state that if , then  contains the th power of a Hamiltonian cycle (Komlós et al. 1996).

---

REFERENCES

Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.

Dirac, G. A. "Some Theorems on Abstract Graphs." Proc. London Math. Soc. 2, 69-81, 1952.

Erdős, P. "Problem 9." In Theory of Graphs and Its Applications, Proceedings of the Symposium held in Smolenice in June 1963 (Ed. M. Fiedler). Prague, Czechoslovakia: Publishing House of the Czechoslovak Academy of Sciences, p. 159, 1964.

Fan, G. and Kierstead, H. A. "Hamiltonian Square-Paths." J. Combin. Theory Ser. B 67, 167-182, 1996.

Kierstead, H. A. and Quintana, J. "Square Hamiltonian Cycles in Graphs with Maximal 4-Cliques." Disc. Math. 178, 81-92, 1998.

Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "On the Square of a Hamiltonian Cycle in Dense Graphs." In Random Structures Algorithms 9, 193-211, 1996.

Seymour, P. Problem Section in Combinatorics: Proceedings of the British Combinatorial Conference, 1973 (Ed. T. P. McDonough and V. C. Mavron). Cambridge, England: Cambridge University Press, pp. 201-202, 1974.

اخر الاخبار

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

ضمن فعاليات مؤتمر السيد المجاهد.. إقامة معرض صور عن المخطوطات الخاصة بمؤلفاته

فعاليات المؤتمر الدولي حول السيد المجاهد تشهد عرض فيلم وثائقي عن حياته ودوره الجهادي

الهيأة العُليا: مؤتمر السيد المجاهد (قدّس سرّه) يسلّط الضوء على إرثه العلمي والفكري ويكشف عن عشرات المؤلفات المحقّقة

العتبة العباسية المقدسة تطلق فعاليات المؤتمر الدولي حول السيد المجاهد وتراثه العلمي

المزيد

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

طبيب يكشف أفضل مكمل غذائي لتحسين المزاج ودعم الصحة النفسية

دراسة جديدة تكشف أضرار الأطعمة الجاهزة على القلب ؟

6 أطعمة طبيعية تهدئ الزكام دون أدوية.. تعرف عليهم

ماذا يحدث لأعراض الزكام عند تناول الثوم بانتظام؟

المزيد

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

ابتكار ثوري في بطاريات السيارات الكهربائية.. سعة أعلى 4 مرات

ماذا يحدث لجسمك عند شرب الماء الساخن يوميا؟

7 فوائد "خفية" لشرب شاي الكركديه كل يوم

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

المزيد

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

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