Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maxim...Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.展开更多
In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and ...In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.展开更多
This paper presents some bounds on the number of Laplacian eigenvalues contained in various subintervals of [0, n] by using the matching number and edge covering number for G, and asserts that for a connected graph th...This paper presents some bounds on the number of Laplacian eigenvalues contained in various subintervals of [0, n] by using the matching number and edge covering number for G, and asserts that for a connected graph the Laplacian eigenvalue 1 appears with certain multiplicity. Furthermore, as an application of our result （Theorem 13）, Grone and Merris＇ conjecture [The Laplacian spectrum of graph II. SIAM J. Discrete Math., 7, 221-229 （1994）] is partially proved.展开更多
基金the National Natural Science Foundation the Doctoral Foundation of the Education Committee of China.
文摘Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.
基金Supported by the National Natural Science Foundation of China (No. 10771091)Com2MaC-KOSEF (No.(E)ndzr09-15)
文摘In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.
基金Supported by National Natural Science Foundation of China （Grant No. 10871204） and the Fundamental Research Funds for the Central Universities （Grant No. 09CX04003A）
文摘This paper presents some bounds on the number of Laplacian eigenvalues contained in various subintervals of [0, n] by using the matching number and edge covering number for G, and asserts that for a connected graph the Laplacian eigenvalue 1 appears with certain multiplicity. Furthermore, as an application of our result （Theorem 13）, Grone and Merris＇ conjecture [The Laplacian spectrum of graph II. SIAM J. Discrete Math., 7, 221-229 （1994）] is partially proved.
