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: o.vacek@vsld.tuzvo.sk
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: