Name
Abstract | ||
|---|---|---|
A graphic sequence pi is potentially H-graphic if there is some realization of pi that contains H as a subgraph. The Erdos-Jacobson-Lehel problem asks one to determine sigma(H, n), the minimum even integer such that any n-term graphic sequence pi with sum at least s (H, n) is potentially H-graphic. The parameter s (H, n) is known as the potential function of H, and can be viewed as a degree sequence variant of the classical extremal function ex(n, H). Recently, Ferrara et al. [Combinatorica 36 (2016), pp. 687-702] determined sigma(H, n) asymptotically for all H, which is analogous to the Erdos-Stone-Simonovits theorem that determines ex(n, H) asymptotically for nonbipartite H. In this paper, we investigate a stability concept for the potential number, inspired by Simonovits' classical result on the stability of the extremal function. We first define a notion of stability for the potential number that is a natural analogue to the stability given by Simonovits. However, under this definition, many families of graphs are not s -stable, establishing a stark contrast between the extremal and potential functions. We then give a sufficient condition for a graph H to be stable with respect to the potential function, and characterize the stability of those graphs H that contain an induced subgraph of order alpha(H) + 1 with exactly one edge. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/16M1109643 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
degree sequence,potentially H-graphic sequence,stability | Integer,Discrete mathematics,Combinatorics,Degree (graph theory),Sigma,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 3 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Catherine Erbes | 1 | 5 | 1.19 |
| Michael Ferrara | 2 | 31 | 10.52 |
| Ryan R. Martin | 3 | 36 | 10.12 |
| Paul Wenger | 4 | 35 | 9.91 |