Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1709854 | Applied Mathematics Letters | 2008 | 5 Pages |
Abstract
A set DD of vertices in a connected graph GG is called a kk-dominating set if every vertex in G−DG−D is within distance kk from some vertex of DD. The kk-domination number of GG, γk(G)γk(G), is the minimum cardinality over all kk-dominating sets of GG. A graph GG is kk-distance domination-critical if γk(G−x)<γk(G)γk(G−x)<γk(G) for any vertex xx in GG. This work considers properties of kk-distance domination-critical graphs and establishes a best possible upper bound on the diameter of a 2-distance domination-critical graph GG, that is, d(G)≤3(γ2−1)d(G)≤3(γ2−1) for γ2≥2γ2≥2.
Keywords
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Fang Tian, Jun-Ming Xu,