Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Extremal problems for forbidden pairs that imply hamiltonicity

100%

Faudree R., Gyárfás A.

Discussiones Mathematicae Graph Theory

|

1999

|

tom 19

|

nr 1

13-29

EN

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.

2

The Ramsey number r(C₇,C₇,C₇)

81%

Faudree R., Schelten A., Schiermeyer I.

Discussiones Mathematicae Graph Theory

|

2003

|

tom 23

|

nr 1

141-158

EN

Bondy and Erdős [2] have conjectured that the Ramsey number for three cycles Cₖ of odd length has value r(Cₖ,Cₖ,Cₖ) = 4k-3. We give a proof that r(C₇,C₇,C₇) = 25 without using any computer support.

3

Pancyclism and small cycles in graphs

81%

Faudree R., Favaron O., Flandrin E., Li H.

Discussiones Mathematicae Graph Theory

|

1996

|

tom 16

|

nr 1

27-40

EN

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (d_C(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.

4

Spanning caterpillars with bounded diameter

81%

Faudree R., Gould R., Jacobson M., Lesniak L.

Discussiones Mathematicae Graph Theory

|

1995

|

tom 15

|

nr 2

111-118

EN

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $cn^{3/4}$ (at most n).

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

4 Faudree R.

1 Favaron O.

1 Flandrin E.

1 Gould R.

1 Gyárfás A.

1 Jacobson M.

1 Lesniak L.

1 Li H.

1 Schelten A.

1 Schiermeyer I.

1 2003

1 1999

1 1996

1 1995

Extremal problems for forbidden pairs that imply hamiltonicity

The Ramsey number r(C₇,C₇,C₇)

Pancyclism and small cycles in graphs

Spanning caterpillars with bounded diameter