Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On the Non-(p−1)-Partite Kp-Free Graphs

100%

Amin K., Faudree J., Gould R. J., Sidorowicz E.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 1

9-23

We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?

Saturation Spectrum of Paths and Stars

88%

Faudree J., Faudree R. J., Gould R. J., Jacobson M. S., Thomas B. J.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 3

811-822

A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from G̅ to G results in a copy of H. The minimum size of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H saturated graphs between sat(n,H) and ex(n,H). In this paper we completely determine the saturation spectrum of stars and we show the saturation spectrum of paths is continuous from sat(n, Pk) to within a constant of ex(n, Pk) when n is sufficiently large.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Faudree J.

2 Gould R. J.

1 Amin K.

1 Faudree R. J.

1 Jacobson M. S.

1 Sidorowicz E.

1 Thomas B. J.

1 2017

1 2013

Wyniki wyszukiwania

On the Non-(p−1)-Partite Kp-Free Graphs

Saturation Spectrum of Paths and Stars