A Variation of the Erdős–Sós Conjecture in Bipartite Graphs

The Erdős–Sós Conjecture states that every graph with average degree more than k - 2 contains all trees of order k as subgraphs. In this paper, we consider a variation of the above conjecture: studying the maximum size of an ( n ,  m )-bipartite graph which does not contain all ( k ,  l )-bipartite...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2017-03, Vol.33 (2), p.503-526
Main Authors: Yuan, Long-Tu, Zhang, Xiao-Dong
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Erdős–Sós Conjecture states that every graph with average degree more than k - 2 contains all trees of order k as subgraphs. In this paper, we consider a variation of the above conjecture: studying the maximum size of an ( n ,  m )-bipartite graph which does not contain all ( k ,  l )-bipartite trees for given integers n ≥ m and k ≥ l . In particular, we determine that the maximum size of an ( n ,  m )-bipartite graph which does not contain all ( n ,  m )-bipartite trees as subgraphs (or all ( k , 2)-bipartite trees as subgraphs, respectively). Furthermore, all these extremal graphs are characterized.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-017-1767-6