Search

For a positive integer k, a graph G is said to have the property I k if each component of G has independence number at most k. The I 1 -admission number of a graph G, denoted by η (G , I 1) , is the cardinality of a smallest vertex subset D such that V (G) = N G [ D ] or each component of G - N G [ D ] is a clique. In this paper, we show that for a connected graph G of order n, if G ∉ { P 3 , C 6 } , then η (G , I 1) ≤ 2 n 7 , and the bound is sharp. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V and let b > a be two positive integers. We say that G has all [a, b]-factors if G has an h-factor for every h : V → N such that a ≤ h (v) ≤ b for every v ∈ V and ∑ v ∈ V h (v) ≡ 0 (mod 2) . A spanning subgraph F of G is called an (a, b)-parity factor, if d F (v) ≡ a ≡ b (mod 2) and a ≤ d F (v) ≤ b for all v ∈ V . In this paper, we have developed sufficient conditions for the existence of all [a, b]-factors and (a, b)-parity factors of G in terms of the independence number and connectivity of G. This work extended an earlier result of Nishimura (J Graph Theory 13: 63–69, 1989). Furthermore, we show that these results are best possible in some cases. [ABSTRACT FROM AUTHOR]