آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,548 |
| تعداد مشاهده مقاله | 1,639,584 |
| تعداد دریافت فایل اصل مقاله | 1,537,161 |
On proximity and other distance parameters in planar graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 28 خرداد 1405 | ||
| نوع مقاله: Special issue of CCO to honor Odile Favaron | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.30964.2684 | ||
| نویسندگان | ||
| Peter Dankelmann* 1؛ Sonwabile Mafunda2؛ Sufiyan Mallu1 | ||
| 1University of Johannesburg, South Africa | ||
| 2Soka University in America, USA | ||
| چکیده | ||
| Let $G$ be a connected graph. The average distance of a vertex $v$ of $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity and remoteness of $G$ are defined as the minimum and maximum, respectively, of the average distances of the vertices of $G$. It was shown by Aouchiche and Hansen [Proximity and remoteness in graphs: bounds and conjectures, Networks 58 no. 2 (2011)] that for a connected graph of order $n$, the difference between remoteness and proximity and the difference between radius and proximity are bounded from above by about $\frac{n}{4}$, and the difference between diameter and proximity is bounded from above by about $\frac{3}{4}n$. In this paper, we show that all three bounds can be improved significantly for simple triangulations (i.e., triangulations), and for graphs of given connectivity. We show that in simple triangulations the above bound on the difference between radius and proximity can be improved to about $\frac{1}{12}n$, and further to about $\frac{1}{16}n$ and $\frac{1}{20}n$ if the graphs is, in addition, $4$-connected or $5$-connected, respectively. Similar improvements are shown for simple quadrangulations (i.e., maximal bipartite planar graphs), and for maximal outerplanar graphs. We further show that the above bound on the difference between remoteness and proximity can be improved to about $\frac{1}{4\kappa}n$ if $G$ is $\kappa$-connected. Finally, we improve the bound on the difference between diameter and proximity to about $\frac{3}{4\kappa}n$ if $G$ is $\kappa$-connected. We present graphs that demonstrate that our bounds are either sharp, or sharp apart from an additive constant, even if restricted to planar graphs. | ||
| کلیدواژهها | ||
| remoteness؛ proximity؛ minimum status؛ outerplanar graph؛ radius | ||
|
آمار تعداد مشاهده مقاله: 3 |
||