Liu and Yan gave the degree condition for a balanced bipartite graph G = （V1, V2; E） to have k vertex-disjoint quadrilaterals containing any given k independent edges e1,……, ek of G, respectively. They also conjec...Liu and Yan gave the degree condition for a balanced bipartite graph G = （V1, V2; E） to have k vertex-disjoint quadrilaterals containing any given k independent edges e1,……, ek of G, respectively. They also conjectured that for any k independent edges e1,……, ek of G, G has a 2-factor with k cycles C1, C2, ……, Ck with respect to {e1, e2,……, ek} such that k - 1 of them are quadrilaterals. In this paper, we prove this conjecture.展开更多
A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥n-factor if its each component admits at least n vertices.A graph G is called P≥n-factor covered if G...A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥n-factor if its each component admits at least n vertices.A graph G is called P≥n-factor covered if G admits a P≥n-factor containing e for any e∈E(G),which is defined by[Discrete Mathematics,309,2067-2076(2009)].We first define the concept of a(P≥n,k)-factor-critical covered graph,namely,a graph G is called(P≥n,k)-factor-critical covered if G-D is P≥n-factor covered for any D⊆V(G)with|D|=k.In this paper,we verify that(i)a graph G withκ(G)≥k+1 is(P≥2,k)-factor-critical covered if bind(G)>2+k/3;(ii)a graph G with|V(G)|≥k+3 andκ(G)≥k+1 is(P≥3,k)-factor-critical covered if bind(G)≥4+k/3.展开更多
基金NNSF of China(10471078)Higher Education of MOE,P.R.C.(2004042204)
文摘Liu and Yan gave the degree condition for a balanced bipartite graph G = （V1, V2; E） to have k vertex-disjoint quadrilaterals containing any given k independent edges e1,……, ek of G, respectively. They also conjectured that for any k independent edges e1,……, ek of G, G has a 2-factor with k cycles C1, C2, ……, Ck with respect to {e1, e2,……, ek} such that k - 1 of them are quadrilaterals. In this paper, we prove this conjecture.
基金Supported by Six Big Talent Peak of Jiangsu Province(Grant No.JY–022)333 Project of Jiangsu Provincethe National Natural Science Foundation of China(Grant No.11371009)。
文摘A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥n-factor if its each component admits at least n vertices.A graph G is called P≥n-factor covered if G admits a P≥n-factor containing e for any e∈E(G),which is defined by[Discrete Mathematics,309,2067-2076(2009)].We first define the concept of a(P≥n,k)-factor-critical covered graph,namely,a graph G is called(P≥n,k)-factor-critical covered if G-D is P≥n-factor covered for any D⊆V(G)with|D|=k.In this paper,we verify that(i)a graph G withκ(G)≥k+1 is(P≥2,k)-factor-critical covered if bind(G)>2+k/3;(ii)a graph G with|V(G)|≥k+3 andκ(G)≥k+1 is(P≥3,k)-factor-critical covered if bind(G)≥4+k/3.
