Premium
Edge proximity conditions for extendability in cubic bipartite graphs
Author(s) -
Aldred R. E. L.,
Jackson Bill
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.20226
Subject(s) - bipartite graph , combinatorics , mathematics , pairwise comparison , graph , enhanced data rates for gsm evolution , cubic graph , complete bipartite graph , foster graph , discrete mathematics , line graph , voltage graph , computer science , statistics , telecommunications
We show that a set M of m edges in a cyclically (3 m − 2)‐edge‐connected cubic bipartite graph is contained in a 1‐factor whenever the edges in M are pairwise distance at least f ( m ) apart, where$$f\left( m \right) = \left\{ {\matrix{{1,} \hfill & {m = 2} \hfill \cr {3,} \hfill & {3 \le m \le 4} \hfill \cr {4,} \hfill & {5 \le m \le 8} \hfill \cr {5,} \hfill & {m \ge 9.} \hfill \cr } } \right.$$ © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 112–120, 2007