Average eccentricity, k-packing and k-domination in graphs

P. Dankelmann, F. J. Osaye

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

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 languageEnglish
Pages (from-to)1261-1274
Number of pages14
JournalDiscrete Mathematics
Volume342
Issue number5
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'Average eccentricity, k-packing and k-domination in graphs'. Together they form a unique fingerprint.

Cite this