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

Abstract

Let \( N_2DL(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_2DL(v) \) for every vertex \( v \). A degree restricted \( 2 \)-switch on edges \( v_1v_2 \) and \( w_1w_2 \), where \( \deg(v_1) = \deg(w_1) \) and \( \deg(v_2) = \deg(w_2) \), is the replacement of a pair of edges \( v_1v_2 \) and \( w_1w_2 \) by the edges \( v_1w_2 \) and \( v_2w_1 \), given that \( v_1w_2 \) and \( v_2w_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.