Premium
Some remarks about factors of graphs
Author(s) -
Correa José R.,
Matamala Martín
Publication year - 2008
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.20284
Subject(s) - combinatorics , mathematics , lambda , graph , discrete mathematics , enhanced data rates for gsm evolution , physics , computer science , telecommunications , quantum mechanics
A ( g , f )‐factor of a graph is a subset F of E such that for all $v \in V$ , $g(v)\le {\rm deg}_{F}(v)\le f(v)$ . Lovasz gave a necessary and sufficient condition for the existence of a ( g , f )‐factor. We extend, to the case of edge‐weighted graphs, a result of Kano and Saito who showed that if $g(v)< \lambda {\rm deg}_{E}(v) < f (v)$ for any $\lambda\in [0,1]$ , then a ( g , f )‐factor always exist. In addition, we use results of Anstee to provide new necessary and sufficient conditions for the existence of a ( g , f )‐factor. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 265–274, 2008