Degree powers and number of stars in graphs with a forbidden broom

2024/01/21 by Gerbner, Dániel
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2401.11587

Abstract

Given a graph G with degree sequence d₁,…, d_n and a positive integer r, let e_r(G)=∑_i=1ⁿ d_i^r. We denote by ex_r(n,F) the largest value of e_r(G) among n-vertex F-free graphs G, and by ex(n,S_r,G) the largest number of stars S_r in n-vertex F-free graphs. The broom B(ℓ,s) is the graph obtained from an ℓ-vertex path by adding s new leaves connected to a penultimate vertex v of the path. We determine ex_r(n,B(ℓ,s)) for r≥ 2, any ℓ,s and sufficiently large n, proving a conjecture of Lan, Liu, Qin and Shi. We also determine ex(n,S_r,B(ℓ,s)) for r≥ 2, any ℓ,s and sufficiently large n.

Related

• On degree powers and counting stars in F-free graphs
• Degree powers in graphs with a forbidden forest
• Degree powers in graphs with forbidden even cycle
• Extremal results on degree powers in some classes of graphs
• Degree powers in graphs with forbidden subgraphs