For a graph G=(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination numberγ(G)of G is the minimum order of a dominating set in G.A graph G is said to...For a graph G=(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination numberγ(G)of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,ifγ(G-v)【γ(G)for any vertex v in G.A graph G is domination edge critical,ifγ(G∪e)【γ(G)for any edge e∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical)if it is domination vertex critical(resp.domination edge critical)andγ(G)=k.Ananchuen and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is k-factor-critical.In this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph.展开更多
In this paper, we investigate the existence of [a,b]-factors with inclusion/exclusion properties under the toughness condition. We prove that if an incomplete graph G satisfies t(G) (a-1) + ab and a,b are two integers...In this paper, we investigate the existence of [a,b]-factors with inclusion/exclusion properties under the toughness condition. We prove that if an incomplete graph G satisfies t(G) (a-1) + ab and a,b are two integers with b > a > 1, then for any two given edges e1 and e2, there exist an [a,b]-factor including e1,e2; and an [a,b]-factor including e1 and excluding e2; as well as an [a,b]-factor excluding e1,e2 unless e1 and e2 have a common end in the case of a = 2. For complete graphs, we obtain a similar result.展开更多
基金supported by Major State Basic Research Development Program of China(973 Project)(Grant No.2006CB805904)Natural Sciences and Engineering Research Council of Canada(Grant No.122059-200)
文摘For a graph G=(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination numberγ(G)of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,ifγ(G-v)【γ(G)for any vertex v in G.A graph G is domination edge critical,ifγ(G∪e)【γ(G)for any edge e∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical)if it is domination vertex critical(resp.domination edge critical)andγ(G)=k.Ananchuen and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is k-factor-critical.In this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph.
基金supported by Natural Sciences and Engineering Research Council of Canada (Grant No. 144073)Shandong University Visiting Scholar FundPCSIRT Project of the Ministry of Education of China
文摘In this paper, we investigate the existence of [a,b]-factors with inclusion/exclusion properties under the toughness condition. We prove that if an incomplete graph G satisfies t(G) (a-1) + ab and a,b are two integers with b > a > 1, then for any two given edges e1 and e2, there exist an [a,b]-factor including e1,e2; and an [a,b]-factor including e1 and excluding e2; as well as an [a,b]-factor excluding e1,e2 unless e1 and e2 have a common end in the case of a = 2. For complete graphs, we obtain a similar result.
