Abstract | ||
---|---|---|
Given a positive integer p
and a graph G with degree sequence d1,…,dn, we define ep(G)=∑i=1ndip. Caro and Yuster introduced a Turán-type problem for ep(G): Given a positive integer p
and a graph H, determine the function exp(n,H), which is the maximum value of ep(G) taken over all graphs G on n vertices that do not contain H as a subgraph. Clearly, ex1(n,H)=2ex(n,H), where ex(n,H) denotes the classical Turán number. Caro and Yuster determined the function exp(n,Pℓ) for sufficiently large n, where p≥2 and Pℓ denotes the path on ℓ vertices. In this paper, we generalise this result and determine exp(n,F) for sufficiently large n, where p≥2 and F is a linear forest. We also determine exp(n,S), where S is a star forest; and exp(n,B), where B is a broom graph with diameter at most six. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.disc.2018.11.013 | Discrete Mathematics |
Keywords | Field | DocType |
Degree power,Turán-type problem,H-free,Forest | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
342 | 3 | 0012-365X |
Citations | PageRank | References |
1 | 0.36 | 2 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yongxin Lan | 1 | 11 | 2.74 |
Henry Liu | 2 | 16 | 5.35 |
Zhongmei Qin | 3 | 20 | 5.22 |
Yongtang Shi | 4 | 511 | 55.83 |