New bounds on proximity and remoteness in graphs
The average distance of a vertex $v$ of a connected graph $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity $\pi(G)$ and the remoteness $\rho(G)$ of $G$ are defined as the minimum and maximum, respectively, average distance of the vert...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Azarbaijan Shahide Madani University
2016-01-01
|
| Series: | Communications in Combinatorics and Optimization |
| Subjects: | |
| Online Access: | http://comb-opt.azaruniv.ac.ir/article_13543.html |
| _version_ | 1818068007554908160 |
|---|---|
| author | P. Dankelmann |
| author_facet | P. Dankelmann |
| author_sort | P. Dankelmann |
| collection | DOAJ |
| description | The average distance of a vertex $v$ of a connected graph $G$
is the arithmetic mean of the distances from $v$ to all
other vertices of $G$. The proximity $\pi(G)$ and the remoteness $\rho(G)$
of $G$ are defined as the minimum and maximum, respectively, average
distance of the vertices of $G$.
In this paper we investigate the difference between proximity or remoteness and the classical distance
parameters diameter and radius.
Among other results we show that in a graph of order
$n$ and minimum degree $\delta$ the difference between
diameter and proximity and the difference between
radius and proximity cannot exceed
$\frac{9n}{4(\delta+1)}+c_1$ and
$\frac{3n}{4(\delta+1)}+c_2$, respectively, for
constants $c_1$ and $c_2$ which depend on $\delta$
but not on $n$. These bounds improve bounds by
Aouchiche and Hansen \cite{AouHan2011} in terms of
order alone by about a factor of $\frac{3}{\delta+1}$.
We further give lower bounds on the remoteness in
terms of diameter or radius. Finally we show that
the average distance of a graph, i.e., the average of
the distances between all pairs of vertices, cannot
exceed twice the proximity. |
| first_indexed | 2024-12-10T15:32:44Z |
| format | Article |
| id | doaj.art-5021e6d3ae9f4e77ab1bb529cecc7846 |
| institution | Directory Open Access Journal |
| issn | 2538-2128 2538-2136 |
| language | English |
| last_indexed | 2024-12-10T15:32:44Z |
| publishDate | 2016-01-01 |
| publisher | Azarbaijan Shahide Madani University |
| record_format | Article |
| series | Communications in Combinatorics and Optimization |
| spelling | doaj.art-5021e6d3ae9f4e77ab1bb529cecc78462022-12-22T01:43:20ZengAzarbaijan Shahide Madani UniversityCommunications in Combinatorics and Optimization2538-21282538-21362016-01-0111294110.22049/CCO.2016.13543New bounds on proximity and remoteness in graphsP. Dankelmann0Department of Pure and Applied Mathematics, University of Johannesburg, \\ PO Box 524 Auckland Park 2006, South AfricaThe average distance of a vertex $v$ of a connected graph $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity $\pi(G)$ and the remoteness $\rho(G)$ of $G$ are defined as the minimum and maximum, respectively, average distance of the vertices of $G$. In this paper we investigate the difference between proximity or remoteness and the classical distance parameters diameter and radius. Among other results we show that in a graph of order $n$ and minimum degree $\delta$ the difference between diameter and proximity and the difference between radius and proximity cannot exceed $\frac{9n}{4(\delta+1)}+c_1$ and $\frac{3n}{4(\delta+1)}+c_2$, respectively, for constants $c_1$ and $c_2$ which depend on $\delta$ but not on $n$. These bounds improve bounds by Aouchiche and Hansen \cite{AouHan2011} in terms of order alone by about a factor of $\frac{3}{\delta+1}$. We further give lower bounds on the remoteness in terms of diameter or radius. Finally we show that the average distance of a graph, i.e., the average of the distances between all pairs of vertices, cannot exceed twice the proximity.http://comb-opt.azaruniv.ac.ir/article_13543.htmlproximity; remoteness; diameter; radius; average distance; Wiener index. |
| spellingShingle | P. Dankelmann New bounds on proximity and remoteness in graphs Communications in Combinatorics and Optimization proximity; remoteness; diameter; radius; average distance; Wiener index. |
| title | New bounds on proximity and remoteness in graphs |
| title_full | New bounds on proximity and remoteness in graphs |
| title_fullStr | New bounds on proximity and remoteness in graphs |
| title_full_unstemmed | New bounds on proximity and remoteness in graphs |
| title_short | New bounds on proximity and remoteness in graphs |
| title_sort | new bounds on proximity and remoteness in graphs |
| topic | proximity; remoteness; diameter; radius; average distance; Wiener index. |
| url | http://comb-opt.azaruniv.ac.ir/article_13543.html |
| work_keys_str_mv | AT pdankelmann newboundsonproximityandremotenessingraphs |