On domination number and distance in graphs

详细信息    查看全文

• 作者：Cong X. Kang ^{kangc@tamug.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Domination number ; Distance ; Diameter ; Spanning tree
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 February 2016
• 年：2016
• 卷：200
• 期：Complete
• 页码：203-206
• 全文大小：372 K

文摘

A vertex set S$S$ of a graph G$G$ is a dominating set   if each vertex of G$G$ either belongs to S$S$ or is adjacent to a vertex in S$S$. The domination number  γ(G)$\gamma \left(G\right)$ of G$G$ is the minimum cardinality of S$S$ as S$S$ varies over all dominating sets of G$G$. It is known that $\gamma \left(G\right)\ge \frac{1}{3}(diam\left(G\right)+1)$, where diam(G)$diam\left(G\right)$ denotes the diameter of G$G$. Define C_r$C_r$ as the largest constant such that γ(G)≥C_r∑_1≤i<j≤rd(x_i,x_j)$\gamma \left(G\right)\ge C_r{\sum }_{1\le i<j\le r}d(x_i,x_j)$ for any bb941db97e6" title="Click to view the MathML source">r$r$ vertices of an arbitrary connected graph G$G$; then $C_2=\frac{1}{3}$ in this view. The main result of this paper is that $C_r=\frac{1}{r(r-1)}$ for r≥3$r\ge 3$. It immediately follows that $\gamma \left(G\right)\ge \mu \left(G\right)=\frac{1}{n(n-1)}W\left(G\right)$, where μ(G)$\mu \left(G\right)$ and W(G)$W\left(G\right)$ are respectively the average distance and the Wiener index of G$G$ of order n$n$. As an application of our main result, we prove a conjecture of DeLaViña et al.  that $\gamma \left(G\right)\ge \frac{1}{2}(ec{c}_G\left(B\right)+1)$, where ecc_G(B)$ec{c}_G\left(B\right)$ denotes the eccentricity of the boundary of an arbitrary connected graph G$G$.