2014/09/14 by Cong X. Kang, Kang, Cong X.
Computer Science · Mathematics · #05C12 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO #msc:05C12 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1409.4116
5 pages, 2 figures
arxiv created 2014/09/14 · openalex publication_date 2014/09/14 · arxiv updated 2014/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex set S of a graph G is a dominating set if each vertex of G either belongs to S or is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality of S as S varies over all dominating sets of G. It is known that γ(G) ≥ (1)/(3)(diam(G)+1), where diam(G) denotes the diameter of G. Define Cr as the largest constant such that γ(G) ≥ Cr ∑1 ≤ i < j ≤ rd(xi, xj) for any r vertices of an arbitrary connected graph G; then C2=(1)/(3) in this view. The main result of this paper is that Cr=(1)/(r(r-1)) for r≥ 3. It immediately follows that γ(G)≥ μ(G)=(1)/(n(n-1))W(G), where μ(G) and W(G) are respectively the average distance and the Wiener index of G of order n. As an application of our main result, we prove a conjecture of DeLaViña et al. that γ(G)≥ (1)/(2)(eccG(B)+1), where eccG(B) denotes the eccentricity of the boundary of an arbitrary connected graph G.