On a conjecture of Fink and Jacobson concerning k-domination and k-dependence |
| |
Authors: | Odile Favaron |
| |
Institution: | L.R.I., U.A. 410 C.N.R.S., Bat. 490, Université Paris-Sud, 91405 Orsay, Cedex, France |
| |
Abstract: | A set D of vertices of a graph is k-dependent if every vertex of D is joined to at most k?1 vertices in D. Let βk(G) be the maximum order of a k-dependent set in G. A set D of vertices of G is k-dominating if every vertex not in D is joined to at least k vertices of D. Let γk(G) be the minimum order of a k-dominating set in G. Here we prove the following conjecture of Fink and Jacobson: for any simple graph G and any positive integer k, γk(G) ≤ βk(G). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|