Let G be a simple graph. A total coloring f of G is called E-total-coloring if no two adjacent vertices of G receive the same color and no edge of G receives the same color as one of its endpoints. For E-total-colorin...Let G be a simple graph. A total coloring f of G is called E-total-coloring if no two adjacent vertices of G receive the same color and no edge of G receives the same color as one of its endpoints. For E-total-coloring f of a graph G and any vertex u of G, let Cf （u） or C（u） denote the set of colors of vertex u and the edges incident to u. We call C（u） the color set of u. If C（u） ≠ C（v） for any two different vertices u and v of V（G）, then we say that f is a vertex-distinguishing E-total-coloring of G, or a VDET coloring of G for short. The minimum number of colors required for a VDET colorings of G is denoted by X^evt（G）, and it is called the VDET chromatic number of G. In this article, we will discuss vertex-distinguishing E-total colorings of the graphs mC3 and mC4.展开更多
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 graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4 be the graph obtained by removing exactly one edge from K4 and let k be an integer with k ≥ 2. We prove that if G ...A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4 be the graph obtained by removing exactly one edge from K4 and let k be an integer with k ≥ 2. We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of K4. The requirement of number five is necessary.展开更多
A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree ...A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree at least four, then G contains k vertex-disjoint copies of K1 ＋ （K1 ∪ KK2）.展开更多
Let k be an integer with k ≥ 2 and G a graph with order n 〉 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n ＋ k, then G contains a vertex cover with exactly k components su...Let k be an integer with k ≥ 2 and G a graph with order n 〉 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n ＋ k, then G contains a vertex cover with exactly k components such that k - 1 of them are chorded 4-cycles. The degree condition is sharp in general.展开更多
An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define ...An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k. The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.展开更多
Lin-Lu-Yau introduced a notion of Ricci curvature for graphs and obtained a complete classification for all Ricci-flat graphs with girth at least five.In this paper,we characterize all Ricci-flat graphs of girth four ...Lin-Lu-Yau introduced a notion of Ricci curvature for graphs and obtained a complete classification for all Ricci-flat graphs with girth at least five.In this paper,we characterize all Ricci-flat graphs of girth four with vertex-disjoint 4-cycles.展开更多
基金Supported by the National Natural Science Foundation of China (Grant No.10771091)the Scientific Research Project of Northwest Normal University (Grant No.NWNU-KJCXGC-03-61)
文摘Let G be a simple graph. A total coloring f of G is called E-total-coloring if no two adjacent vertices of G receive the same color and no edge of G receives the same color as one of its endpoints. For E-total-coloring f of a graph G and any vertex u of G, let Cf （u） or C（u） denote the set of colors of vertex u and the edges incident to u. We call C（u） the color set of u. If C（u） ≠ C（v） for any two different vertices u and v of V（G）, then we say that f is a vertex-distinguishing E-total-coloring of G, or a VDET coloring of G for short. The minimum number of colors required for a VDET colorings of G is denoted by X^evt（G）, and it is called the VDET chromatic number of G. In this article, we will discuss vertex-distinguishing E-total colorings of the graphs mC3 and mC4.
基金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.
基金This work was supported in part by the National Natural Science Foundation of China （Grant Nos. 11161035, 11401455） and the Fundamental Research Funds for the Central Universities （No. K5051370010）.
文摘A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4 be the graph obtained by removing exactly one edge from K4 and let k be an integer with k ≥ 2. We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of K4. The requirement of number five is necessary.
基金Supported by National Natural Science Foundation of China(Grant Nos.11161035 and 11226292)Ningxia Ziran(Grant No.NZ1153)research grant from Ningxia University(Grant No.zr1122)
文摘A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree at least four, then G contains k vertex-disjoint copies of K1 ＋ （K1 ∪ KK2）.
基金Supported by Natural Science Foundation of China （Grant Nos. 11161035, 10801091）, Research Crants from Ningxia University （Grant No. （E）ndzr09-1） and Scientific Research Project in Xinjiang （Grant No. XJEDU2009S101）
文摘Let k be an integer with k ≥ 2 and G a graph with order n 〉 4k. We prove that if the minimum degree sum of any two nonadjacent vertices is at least n ＋ k, then G contains a vertex cover with exactly k components such that k - 1 of them are chorded 4-cycles. The degree condition is sharp in general.
基金Foundation item： the National Natural Science Foundation of China （No. 10626029）.
文摘An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k. The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.
基金Supported by the National Natural Science Foundation of China(Grant Nos.11601093,12025109,12071489 and 61976104)the Research Fund of Guangdong University of Foreign Studies(Grant Nos.299-X5219228 and 297-ZW200011)。
文摘Lin-Lu-Yau introduced a notion of Ricci curvature for graphs and obtained a complete classification for all Ricci-flat graphs with girth at least five.In this paper,we characterize all Ricci-flat graphs of girth four with vertex-disjoint 4-cycles.
