آمار
| تعداد نشریات | 7 |
| تعداد شمارهها | 102 |
| تعداد مقالات | 1,141 |
| تعداد مشاهده مقاله | 1,048,771 |
| تعداد دریافت فایل اصل مقاله | 867,882 |
New bounds on proximity and remoteness in graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 3، دوره 1، شماره 1، شهریور 2016، صفحه 29-41 اصل مقاله (423.13 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2016.13543 | ||
| نویسنده | ||
| P. Dankelmann* | ||
| University of Johannesburg | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| diameter؛ radius؛ proximity؛ remoteness؛ distance | ||
| مراجع | ||
|
[1] M. Aouchiche, G. Caporossi, and P. Hansen. Variable Neighbourhood Search for Extremal Graphs, 20 Automated Comparison of Graph Invariants. MATCH Commun. Math. Comput. Chem. 58 (2007), 365-384.
[2] M. Aouchiche and P. Hansen. Nordhaus-Gaddum relations for proximity and remoteness in graphs. Comput. Math. Appl. 59(no. 8) (2010), 2827-2835.
[3] M. Aouchiche, P. Hansen. Proximity and remoteness in graphs: results and conjectures. Networks 58 (no. 2) (2011), 95-102.
[4] C.A. Barefoot, R.C. Entringer, and L.A. Sz´ekely. Extremal values for ratios of distances in trees. Discrete Appl. Math. 80 (1997), 37-56.
[5] P. Dankelmann,G. Dlamini, and H.C. Swart. Uppper bounds on distance measures in K2,l-free graphs. (manuscript)
[6] P. Dankelmann. Proximity, remoteness, and minimum degree. Discrete Appl. Math. 184 (2015), 223-228.
[7] G. Dlamini. Aspects of distances in graphs, Ph.D. Thesis, University of Natal, Durban, 2003. [8] R.C. Entringer, D.E. Jackson, and D.A. Snyder. Distance in graphs. Czechoslovak Math. J. 26 (101) no. 2 (1976), 283-296.
[9] P. Erd¨os, J. Pach,R. Pollack, and Z. Tuza. Radius, diameter, and minimum degree. J. Combin. Theory Ser. B 47 (1989) 73-79.
[10] B. Ma, B. Wu, and W. Zhang. Proximity and average eccentricity of a graph. Inform. Process. Lett. 112(no. 10) (2012), 392-395.
[11] B. Wu and W. Zhang. Average distance, radius and remoteness of a graph. Ars Math. Contemp. 7 (2014), 441-452.
[12] B. Zelinka. Medians and peripherians of trees. Arch. Math. (Brno) 4 (1968), 87-95.
| ||
|
آمار تعداد مشاهده مقاله: 1,753 تعداد دریافت فایل اصل مقاله: 1,925 |
||