کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648140 1342394 2012 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The edge spectrum of the saturation number for small paths
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The edge spectrum of the saturation number for small paths
چکیده انگلیسی

Let HH be a simple graph. A graph GG is called an HH-saturated graph if HH is not a subgraph of GG, but adding any missing edge to GG will produce a copy of HH. Denote by SAT(n,H)SAT(n,H) the set of all HH-saturated graphs GG with order nn. Then the saturation number sat(n,H)sat(n,H) is defined as minG∈SAT(n,H)|E(G)|minG∈SAT(n,H)|E(G)|, and the extremal number ex(n,H)ex(n,H) is defined as maxG∈SAT(n,H)|E(G)|maxG∈SAT(n,H)|E(G)|. A natural question is that of whether we can find an HH-saturated graph with mm edges for any sat(n,H)≤m≤ex(n,H)sat(n,H)≤m≤ex(n,H). The set of all possible values mm is called the edge spectrum for HH-saturated graphs. In this paper we investigate the edge spectrum for PiPi-saturated graphs, where 2≤i≤62≤i≤6. It is trivial for the case of P2P2 that the saturated graph must be an empty graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2682–2689
نویسندگان
, , , ,