Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T18:14:16.626Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructing Trees in Graphs whose Complement has no K2,s

Published online by Cambridge University Press:  06 September 2002

EDWARD DOBSON
EDWARD DOBSON
Affiliation:
Department of Mathematics and Statistics, PO Drawer MA, Mississippi State University, Mississippi State, MS 39762, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that, if G is a graph of order n with maximal degree Δ(G) and minimal degree δ(G) whose complement contains no K2,s, s [ges ] 2, then G contains every tree T of order n−s+1 whose maximal degree is at most Δ(G) and whose vertex of second-largest degree is at most δ(G). We then show that this result implies that special cases of two conjectures are true. We verify that the Erdös–Sós conjecture, which states that a graph whose average degree is larger than k−1 contains every tree of order k+1, is true for graphs whose complement does not contain a K2,4, and the Komlós–Sós conjecture, which states that every graph of median degree at least k contains every tree of order k+1, is true for graphs whose complement does not contain a K2,3.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 4 , July 2002 , pp. 343 - 347
Copyright
2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)