Premium
Constructing trees in graphs with no K 2, s
Author(s) -
Balasubramanian Suman,
Dobson Edward
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20261
Subject(s) - combinatorics , mathematics , conjecture , graph , degree (music) , integer (computer science) , order (exchange) , discrete mathematics , computer science , physics , acoustics , programming language , finance , economics
Let s ≥ 2 be an integer and k > 12( s − 1) an integer. We give a necessary and sufficient condition for a graph G containing no K 2, s with $\delta(G)\ge{k}/2$ and $\Delta(G)\ge k$ to contain every tree T of order k + 1. We then show that every graph G with no K 2, s and average degree greater than k − 1 satisfies this condition, improving a result of Haxell, and verifying a special case of the Erdős—Sós conjecture, which states that every graph of average degree greater than k − 1 contains every tree of order k + 1. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 301–310, 2007