Previous |  Up |  Next


radius of graph; radius-invariant graphs
The eccentricity $e(v)$ of a vertex $v$ is defined as the distance to a farthest vertex from $v$. The radius of a graph $G$ is defined as a $r(G)=\min _{u \in V(G)}\lbrace e(u)\rbrace $. A graph $G$ is radius-edge-invariant if $r(G-e)=r(G)$ for every $e \in E(G)$, radius-vertex-invariant if $r(G-v)= r(G)$ for every $v \in V(G)$ and radius-adding-invariant if $r(G+e)=r(G)$ for every $e \in E(\overline{G})$. Such classes of graphs are studied in this paper.
[1] Buckley, F., Harary, F.: Distance in Graphs. Addison-Wesley, Redwood City, 1990.
[2] Buckley, F., Itagi K. M., Walikar, H. B.: Radius-edge-invariant and diameter-edge-invariant graphs. Discrete Math. 272 (2003), 119–126. DOI 10.1016/S0012-365X(03)00189-4 | MR 2019205
[3] Buckley, F., Lewinter, M.: Graphs with all diametral paths through distant central nodes. Math. Comput. Modelling 17 (1990), 35–41. DOI 10.1016/0895-7177(93)90250-3 | MR 1236507
[4] Dutton, R. D., Medidi, S. R., Brigham, R. C.: Changing and unchanging of the radius of graph. Linear Algebra Appl. 217 (1995), 67–82. MR 1322543
[5] Frucht, R., Harary, F.: On the corona of two graphs. Aequationes Math. 4 (1970), 322–325. DOI 10.1007/BF01844162 | MR 0281659
[6] Gliviak, F.: On radially extremal graphs and digraphs, a survey. Math. Bohem. 125 (2000), 215–225. MR 1768809 | Zbl 0963.05072
[7] Graham, N., Harary, F.: Changing and unchanging the diameter of a hypercube. Discrete Appl. Math. 37/38 (1992), 265–274. DOI 10.1016/0166-218X(92)90137-Y | MR 1176857
[8] Harary, F.: Changing and unchanging invariants for graphs. Bull. Malaysian Math. Soc. 5 (1982), 73–78. MR 0700121 | Zbl 0512.05035
[9] Vizing, V. G.: The number of edges in a graph of given radius. Dokl. Akad. Nauk 173 (1967), 1245–1246. (Russian) MR 0210622 | Zbl 0158.42504
Partner of
EuDML logo