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

N. Benakli; E. Halleck; S. R. Kingan

paper

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

arXiv:1909.08722

Abstract

Let $N_{2} D L (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} D L (v)$ for every vertex $v$ . A degree restricted $2$ -switch on edges $v_{1} v_{2}$ and $w_{1} w_{2}$ , where $d e g (v_{1}) = d e g (w_{1})$ and $d e g (v_{2}) = d e g (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.