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.展开更多
A set D of vertices of a graph G = (V, E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a ...A set D of vertices of a graph G = (V, E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed's result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most (3n +IV21)/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk (G, γ) ≤ (3n+5k)/8 for all graphs of order n with minimum degree at least 3.展开更多
基金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 Korea Research Foundation Grant (KRF-2002-015-cp0050)the National Natural Science Foundation of China (Grant Nos. 60773078, 10571117)+3 种基金the ShuGuang Plan of Shanghai Education Development Foundation (Grant No. 06SG42)M. A. Henning is supported in part by the South African National Research Foundationthe University of KwaZulu-Natalsupported by Shanghai Leading Academic Discipline Project (No. $30104)
文摘A set D of vertices of a graph G = (V, E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed's result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most (3n +IV21)/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk (G, γ) ≤ (3n+5k)/8 for all graphs of order n with minimum degree at least 3.