A characterization of 2-neighborhood degree list of diameter 2 graphs

Abstract

Let $N_{2}DL(v)$ denote the set of degrees of vertices at distance $2$ from $v$. The $2$-neighborhood degree list of a graph is a listing of $N_{2}DL(v)$ for every vertex $v$. A degree restricted $2$-switch on edges $v_1{v}_2$ and $w_1{w}_2$, where $\mathrm{deg}(v_1)=\mathrm{deg}(w_1)$ and $\mathrm{deg}(v_2)=\mathrm{deg}(w_2)$, is the replacement of a pair of edges $v_1{v}_2$ and $w_1{w}_2$ by the edges $v_1{w}_2$ and $v_2{w}_1$, given that $v_1{w}_2$ and $v_2{w}_1$ did not appear in the graph originally. Let $G$ and $H$ be two graphs of diameter $2$ on the same vertex set. We prove that $G$ and $H$ have the same $2$-neighborhood degree list if and only if $G$ can be transformed into $H$ by a sequence of degree restricted $2$-switches.