کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648140 | 1342394 | 2012 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2682–2689