Advanced Search

The concepts of critical and cocritical radius edge-invariant graphs are introduced. We prove that every graph can be embedded as an induced subgraph of a critical or cocritical radius-edge-invariant graph. We show that every cocritical radius-edge-invariant graph of radius r ≥ 15 must have at least 3r+2 vertices.

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\left(G\right)$ for all its edges, diameter-vertex-invariant, if $d(G-v)=d\left(G\right)$ for all its vertices and diameter-adding-invariant if $d(G+e)=d\left(e\right)$ 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.

The eccentricity $e\left(v\right)$ 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\left(G\right)={min}_{u\in V\left(G\right)}\left\{e\left(u\right)\right\}$. A graph $G$ is radius-edge-invariant if $r(G-e)=r\left(G\right)$ for every $e\in E\left(G\right)$, radius-vertex-invariant if $r(G-v)=r\left(G\right)$ for every $v\in V\left(G\right)$ and radius-adding-invariant if $r(G+e)=r\left(G\right)$ for every $e\in E\left(\overline{G}\right)$. Such classes of graphs are studied in this paper.