کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648927 1632446 2007 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum degree and the minimum size of K2t-saturated graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Minimum degree and the minimum size of K2t-saturated graphs
چکیده انگلیسی

A graph G is said to be F-saturated if G does not contain a copy of F   as a subgraph and G+eG+e contains a copy of F as a subgraph for any edge e contained in the complement of G. Erdős et al. in [A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107–1110.] determined the minimum   number of edges, sat(n,F)sat(n,F), such that a graph G on n vertices must have when F is a t  -clique. Later, Ollmann [K2,2K2,2-saturated graphs with a minimal number of edges, in: Proceedings of the Third SouthEast Conference on Combinatorics, Graph Theory and Computing, 1972, pp. 367–392.] determined sat(n,F)sat(n,F) for F=K2,2F=K2,2. Here we give an upper bound for sat(n,F)sat(n,F) when F=Kt2 the complete t-partite graph with partite sets of size 2, and prove equality when G is of prescribed minimum degree.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 9–10, 6 May 2007, Pages 1108–1114
نویسندگان
, ,