Previous |  Up |  Next

Article

Title: Diameter-invariant graphs (English)
Author: Vacek, Ondrej
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 130
Issue: 4
Year: 2005
Pages: 355-370
Summary lang: English
.
Category: math
.
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. (English)
Keyword: extremal graphs
Keyword: diameter of graph
Keyword: distance
MSC: 05C12
MSC: 05C35
idZBL: Zbl 1112.05033
idMR: MR2182382
DOI: 10.21136/MB.2005.134211
.
Date available: 2009-09-24T22:22:21Z
Last updated: 2020-07-29
Stable URL: http://hdl.handle.net/10338.dmlcz/134211
.
Reference: [1] V. Bálint, O. Vacek: Radius-invariant graphs.Math. Bohem. 129 (2004), 361–377. MR 2102610
Reference: [2] F. Buckley, F. Harary: Distance in Graphs.Addison-Wesley, Redwood City, 1990. MR 1045632
Reference: [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
Reference: [4] R. Frucht, F. Harary: On the corona of two graphs.Aequationes Math. 4 (1970), 322–325. MR 0281659, 10.1007/BF01844162
Reference: [5] F. Gliviak: On radially extremal graphs and digraphs, a survey.Math. Bohem. 125 (2000), 215–225. Zbl 0963.05072, MR 1768809
Reference: [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
Reference: [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
Reference: [8] N. Graham, F. Harary: Changing and unchanging the diameter of a hypercube.Discrete Appl. Math. 37/38 (1992), 265–274. MR 1176857
Reference: [9] F. Harary: Changing and unchanging invariants for graphs.Bull Malaysian Math. Soc. 5 (1982), 73–78. Zbl 0512.05035, MR 0700121
Reference: [10] S. M. Lee: Design of diameter $e$-invariant networks.Congr. Numerantium 65 (1988), 89–102. Zbl 0800.05011, MR 0992859
Reference: [11] S. M. Lee, R. Tanoto: Three classes of diameter $e$-invariant graphs.Comment. Math. Univ. Carolin. 28 (1987), 227–232. MR 0904748
Reference: [12] J. Plesník: Critical graphs of given diameter.Acta Fac. Rer. Nat. Univ. Comenianae, Math. 30 (1975), 71–93. MR 0398904
Reference: [13] H. B. Walikar, F. Buckley, K. M. Itagi: Radius-edge-invariant and diameter-edge-invariant graphs.Discrete Math. 272 (2003), 119–126. MR 2019205, 10.1016/S0012-365X(03)00189-4
.

Files

Files Size Format View
MathBohem_130-2005-4_3.pdf 407.9Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo