- Tytuł:
- Extremal problems for forbidden pairs that imply hamiltonicity
- Autorzy:
-
Faudree, Ralph
Gyárfás, András - Powiązania:
- https://bibliotekanauki.pl/articles/744237.pdf
- Data publikacji:
- 1999
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Opis:
- Let C denote the claw $K_{1,3}$, N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and $Z_i$ the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does not contain an induced copy of C or of Y) will be determined for Y a connected subgraph of either P₆, N, W, or Z₃. It should be noted that the pairs of graphs CY are precisely those forbidden pairs that imply that any 2-connected graph of order at least 10 is hamiltonian. These extremal numbers give one measure of the relative strengths of the forbidden subgraph conditions that imply a graph is hamiltonian.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1999, 19, 1; 13-29
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki