Abstract
Let G be a connected graph. The eccentricity e(v) of a vertex v is the distance from v to a vertex farthest from v. The average eccentricity avec(G) of G is defined as the average of the eccentricities of the vertices of G, i.e., as [Formula presented]∑v∈Ve(v), where V is the vertex set of G. For k∈N, the k-packing number of G is the largest cardinality of a set of vertices of G whose pairwise distance is greater than k. A k-dominating set of G is a set S of vertices such that every vertex of G is within distance k from some vertex of S. The k-domination number (connected k-domination number) of G is the minimum cardinality of a k-dominating set (of a k-dominating set that induces a connected subgraph) of G. For k=1, the k-packing number, the k-domination number and the connected k-domination number are the independence number, the domination number and the connected domination number, respectively. In this paper we present upper bounds on the average eccentricity of graphs in terms of order and either k-packing number, k-domination number or connected k-domination number.
Original language | English |
---|---|
Pages (from-to) | 1261-1274 |
Number of pages | 14 |
Journal | Discrete Mathematics |
Volume | 342 |
Issue number | 5 |
DOIs | |
Publication status | Published - May 2019 |
Keywords
- Average eccentricity
- Domination number
- Eccentricity
- Independence number
- Packing number
- Total eccentricity
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics