Average distances and distance domination numbers |
| |
Authors: | Fang Tian |
| |
Institution: | a Department of Applied Mathematics, Shanghai University of Finance and Economics, Shanghai, 200433, China b Department of Mathematics, University of Science and Technology of China, Hefei, 230026, China |
| |
Abstract: | Let k be a positive integer and G be a simple connected graph with order n. The average distance μ(G) of G is defined to be the average value of distances over all pairs of vertices of G. A subset D of vertices in G is said to be a k-dominating set of G if every vertex of V(G)−D is within distance k from some vertex of D. The minimum cardinality among all k-dominating sets of G is called the k-domination number γk(G) of G. In this paper tight upper bounds are established for μ(G), as functions of n, k and γk(G), which generalizes the earlier results of Dankelmann P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997) 21-35] for k=1. |
| |
Keywords: | Distance Average distance Diameter Domination number Distance domination number |
本文献已被 ScienceDirect 等数据库收录! |
|