Premium
Graphic Sequences Have Realizations Containing Bisections of Large Degree
Author(s) -
Hartke Stephen G.,
Seacrest Tyler
Publication year - 2012
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.20652
Subject(s) - combinatorics , conjecture , mathematics , bipartite graph , disjoint sets , realization (probability) , bisection , graph , degree (music) , discrete mathematics , upper and lower bounds , geometry , physics , mathematical analysis , statistics , acoustics
A bisection of a graph is a balanced bipartite spanning sub‐graph. Bollobás and Scott conjectured that every graph G has a bisection H such that deg H ( v ) ≥ ⌊deg G ( v )/2⌋ for all vertices v . We prove a degree sequence version of this conjecture: given a graphic sequence π, we show that π has a realization G containing a bisection H where deg H ( v ) ≥ ⌊(deg G ( v ) − 1)/2⌋ for all vertices v . This bound is very close to best possible. We use this result to provide evidence for a conjecture of Brualdi (Colloq. Int. CNRS, vol. 260, CNRS, Paris) and Busch et al. (2011), that if π and π − k are graphic sequences, then π has a realization containing k edge‐disjoint 1‐factors. We show that if the minimum entry δ in π is at least n /2 + 2, then π has a realization containing edge‐disjoint 1‐factors. We also give a construction showing the limits of our approach in proving this conjecture. © 2011 Wiley Periodicals, Inc. J Graph Theory