Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: saturated graphs

Sortuj według:

Ogranicz wyniki do:

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

On some variations of extremal graph problems

100%

Semanišin G.

Discussiones Mathematicae Graph Theory

1997

tom 17

nr 1

67-76

A set P of graphs is termed hereditary property if and only if it contains all subgraphs of any graph G belonging to P. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) whenever it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has a the maximum number of edges among all P-maximal graphs of given order. The number of its edges is denoted by ex(n, P). If the number of edges of a P-maximal graph is minimum, then the graph is called P-saturated and its number of edges is denoted by sat(n, P). In this paper, we consider two famous problems of extremal graph theory. We shall translate them into the language of P-maximal graphs and utilize the properties of the lattice of all hereditary properties in order to establish some general bounds and particular results. Particularly, we shall investigate the behaviour of sat(n,P) and ex(n,P) in some interesting intervals of the mentioned lattice.

Weak Saturation Numbers for Sparse Graphs

100%

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

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 4

677-693

For a fixed graph F, a graph G is F-saturated if there is no copy of F in G, but for any edge e ∉ G, there is a copy of F in G + e. The minimum number of edges in an F-saturated graph of order n will be denoted by sat(n, F). A graph G is weakly F-saturated if there is an ordering of the missing edges of G so that if they are added one at a time, each edge added creates a new copy of F. The minimum size of a weakly F-saturated graph G of order n will be denoted by wsat(n, F). The graphs of order n that are weakly F-saturated will be denoted by wSAT(n, F), and those graphs in wSAT(n, F) with wsat(n, F) edges will be denoted by wSAT(n, F). The precise value of wsat(n, T) for many families of sparse graphs, and in particular for many trees, will be determined. More specifically, families of trees for which wsat(n, T) = |T|−2 will be determined. The maximum and minimum values of wsat(n, T) for the class of all trees will be given. Some properties of wsat(n, T) and wSAT(n, T) for trees will be discussed. Keywords: saturated graphs, sparse graphs, weak saturation.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Faudree R. J.

1 Gould R. J.

1 Jacobson M. S.

1 Semanišin G.

1 2013

1 1997

Wyniki wyszukiwania

On some variations of extremal graph problems

Weak Saturation Numbers for Sparse Graphs