Average eccentricity, minimum degree and maximum degree in graphs
- PDF / 447,968 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 224 Views
Average eccentricity, minimum degree and maximum degree in graphs P. Dankelmann1
· F. J. Osaye1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let G be a connected finite graph with vertex set V (G). The eccentricity e(v) of a vertex v is the distance from v to a vertex farthest from v. The average eccentricity 1 of G is defined as |V (G)| v∈V (G) e(v). We show that the average eccentricity of a connected graph of order n, minimum degree δ and maximum degree does not −δ 1+ +7, and this bound is sharp apart from an additive constant. exceed 49 n−−1 δ+1 3n We give improved bounds for triangle-free graphs and for graphs not containing 4cycles. Keywords Average eccentricity · Distance · Minimum degree · Maximum degree · Eccentricity · Graph
1 Introduction Let G be a connected graph with vertex set V (G). The eccentricity e(v) of a vertex is the maximum distance between v and a vertex in G. The average eccentricity avec(G) of G is the average of the eccentricities of the vertices of G, i.e., avec(G) = 1 u∈V (G) e(u). The average eccentricity was first introduced by Buckley and |V (G)| Harary (1990) under the name eccentric mean. Its systematic study was initiated by Dankelmann et al. (2004), who established an upper bound on the average eccentricity in terms of order and minimum degree, and further showed among other results, that the path maximizes the average eccentricity among all connected graphs of given order.
P. Dankelmann: Financial Support by the South African National Research Foundation, Grant Number 118521, is gratefully acknowledged. F.J. Osaye: The results presented in this paper form part of the second author’s PhD thesis.
B 1
P. Dankelmann [email protected] University of Johannesburg, Johannesburg, South Africa
123
Journal of Combinatorial Optimization
Proposition 1 (Dankelmann et al. 2004) Let G be a connected graph of order n. Then 1 avec(G) ≤ n
3n 2 n − , 4 2
and this bound is sharp. We first recall some upper bounds on the average eccentricity of a connected graph involving the minimum degree. Dankelmann et al. (2004) showed that if G is a graph of order n and minimum degree δ ≥ 2, then avec(G) ≤
15 9n + , 4(δ + 1) 4
(1)
and this bound is sharp apart from a small additive constant. By applying a similar technique, it was recently proved in Dankelmann et al. (2019) that if G is triangle-free, then the bound (1) can be improved to avec(G) ≤ 3
n + 5, 2δ
(2)
and for C4 -free graphs to 15 avec(G) ≤ 4
n δ2
− 2 2δ + 1
+
11 . 2
(3)
Moreover, it was shown that the bound in (2) is sharp apart from a small additive constant and that, for δ + 1 a prime power, there exists an infinite number of C4 -free graphs of minimum degree at least δ with avec(G) ≥
n 5 15 − . 2 4 δ + 3δ + 2 2
Other recent results on the average eccentricity of graphs can be found, for example, in Ali et al. (2018), Dankelmann and Mukwembi (2014), Dankelmann and Osaye (2019), Dankelmann et al. (2019), Darabi et al. (2018), Du and Ili˘c (2013), Du and Ili˘c
Data Loading...
