MATHEMATICA BOHEMICA, Vol. 130, No. 4, pp. 355-370 (2005)

Diameter-invariant graphs

Ondrej Vacek

Ondrej Vacek, Department of Mathematics and Descriptive Geometry, Faculty of Wood Sciences and Technology, Technical University Zvolen, T. G. Masaryka 24, 960 53 Zvolen, Slovak Republic, e-mail:

Abstract: 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.

Keywords: extremal graphs, diameter of graph

Classification (MSC2000): 05C12, 05C35

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]
© 2005–2010 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition