- Tytuł:
- Chvátals Condition cannot hold for both a graph and its complement
- Autorzy:
-
Kostochka, Alexandr
West, Douglas - Powiązania:
- https://bibliotekanauki.pl/articles/743881.pdf
- Data publikacji:
- 2006
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Hamiltonian cycle
Chvátal's Condition
random graph - Opis:
- Chvátal's Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_i > i$ or $d_{n-i} ≥ n-i$. We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 73-76
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł