Average distances and distance domination numbers. (English) Zbl 1169.05318
Summary: Let \(k\) be a positive integer and \(G\) be a simple connected graph with order \(n\). The average distance \(\mu (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 \(\gamma _k(G)\) of \(G\). In this paper tight upper bounds are established for \(\mu (G)\), as functions of \(n, k\) and \(\gamma _k(G)\), which generalizes the earlier results of P. Dankelmann [”Average distance and domination number,” Discrete Appl. Math. 80, No.1, 21–35 (1997; Zbl 0888.05024)] for \(k=1\).
MSC:
| 05C12 | Distance in graphs |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 0888.05024References:
| [1] | Beezer, R. A.; Riegsecker, J. E.; Smith, B. A., Using minimum degree to bound average distance, Discrete Math., 226, 365-371 (2001) · Zbl 0959.05038 |
| [2] | Bienstock, D.; Gyori, E., Average distance in graphs with removed elements, J. Graph Theory, 12, 375-390 (1988) · Zbl 0695.05032 |
| [3] | G.J. Chang, \(k\); G.J. Chang, \(k\) |
| [4] | Chang, G. J.; Nemhauser, G. L., The \(k\)-domination and \(k\)-stability problems on sun-free chordal graphs, SIAM J. Algebr. Discrete Methods, 5, 332-345 (1984) · Zbl 0576.05054 |
| [5] | Chung, F. R.K.; Coffman, E. G.; Reiman, M. I.; Simon, B., The forwarding index of communication networks, IEEE Trans. Inform. Theory, 33, 2, 224-232 (1987) · Zbl 0626.94019 |
| [6] | Dankelmann, P., Average distance and domination number, Discrete Appl. Math., 80, 21-35 (1997) · Zbl 0888.05024 |
| [7] | Dankelmann, P.; Oellermann, O. R.; Swart, H. C., Average distance and independence number, Discrete Appl. Math., 51, 75-83 (1994) · Zbl 0803.05020 |
| [8] | Firby, P.; Haviland, J., Independence and average distance in graphs, Discrete Appl. Math., 75, 27-37 (1997) · Zbl 0880.05030 |
| [9] | Gutman, I.; Polansky, O. E., Mathematical Concepts in Organic Chemistry (1986), Springer: Springer Berlin · Zbl 0657.92024 |
| [10] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 |
| [11] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs (Advanced Topics) (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0883.00011 |
| [12] | Heydemann, M. C.; Meyer, J. C.; Sotteau, D., On forwarding indices of networks, Discrete Appl. Math., 23, 103-123 (1989) · Zbl 0681.90077 |
| [13] | Hosoya, H., Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn., 4, 2332-2339 (1971) |
| [14] | Meir, A.; Moon, J. W., Relations between packing and covering numbers of a tree, Pacific J. Math., 61, 1, 225-233 (1975) · Zbl 0315.05102 |
| [15] | Plesnik, J., On the sum of all distances in a graph or digraph, J. Graph Theory, 8, 1-21 (1984) · Zbl 0552.05048 |
| [16] | Tomescu, I., On the sum of all distances in chromatic blocks, J. Graph Theory, 18, 83-102 (1994) · Zbl 0789.05036 |
| [17] | Wiener, H., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 17-20 (1949) |
| [18] | Xu, J.-M., Theory and Application of Graphs (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 1035.05003 |
| [19] | Zelinka, B., Medians and peripherians of trees, Arch. Math.(Brno), 4, 87-95 (1968) · Zbl 0206.26105 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
