Article ID Journal Published Year Pages File Type
4648140 Discrete Mathematics 2012 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,