Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
extremal graphs; diameter of graph; distance
extremal graphs; diameter of graph; distance
Summary:
The diameter of a graph $G$ is the maximal distance between two vertices of $G$. A graph $G$ is said to be diameter-edge-invariant, if $d(G-e)=d(G)$ for all its edges, diameter-vertex-invariant, if $d(G-v)=d(G)$ for all its vertices and diameter-adding-invariant if $d(G+e)=d(e)$ for all edges of the complement of the edge set of $G$. This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.
References:
[1] V. Bálint, O. Vacek: Radius-invariant graphs. Math. Bohem. 129 (2004), 361–377. MR 2102610
[2] F. Buckley, F. Harary: Distance in Graphs. Addison-Wesley, Redwood City, 1990. MR 1045632
[3] R. D. Dutton, S. R. Medidi, R. C. Brigham: Changing and unchanging of the radius of graph. Linear Algebra Appl. 217 (1995), 67–82. MR 1322543
[4] R. Frucht, F. Harary: On the corona of two graphs. Aequationes Math. 4 (1970), 322–325. DOI 10.1007/BF01844162 | MR 0281659
[5] F. Gliviak: On radially extremal graphs and digraphs, a survey. Math. Bohem. 125 (2000), 215–225. MR 1768809 | Zbl 0963.05072
[6] F. Glivjak: On certain classes of graphs of diameter two without superfluous edges. Acta Fac. Rer. Nat. Univ. Comenianae, Math. 21 (1968), 39–48. MR 0265197
[7] F. Glivjak, P. Kyš, J. Plesník: On the extension of graphs with a given diameter without superfluous edges. Mat. Cas. Slovensk. Akad. Vied 19 (1969), 92–101. MR 0302503
[8] N. Graham, F. Harary: Changing and unchanging the diameter of a hypercube. Discrete Appl. Math. 37/38 (1992), 265–274. MR 1176857
[9] F. Harary: Changing and unchanging invariants for graphs. Bull Malaysian Math. Soc. 5 (1982), 73–78. MR 0700121 | Zbl 0512.05035
[10] S. M. Lee: Design of diameter $e$-invariant networks. Congr. Numerantium 65 (1988), 89–102. MR 0992859 | Zbl 0800.05011
[11] S. M. Lee, R. Tanoto: Three classes of diameter $e$-invariant graphs. Comment. Math. Univ. Carolin. 28 (1987), 227–232. MR 0904748
[12] J. Plesník: Critical graphs of given diameter. Acta Fac. Rer. Nat. Univ. Comenianae, Math. 30 (1975), 71–93. MR 0398904
[13] H. B. Walikar, F. Buckley, K. M. Itagi: Radius-edge-invariant and diameter-edge-invariant graphs. Discrete Math. 272 (2003), 119–126. DOI 10.1016/S0012-365X(03)00189-4 | MR 2019205
Search
Partner of
