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

Publication date 18 September 2019

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.

This page was built for publication: A characterization of 2-neighborhood degree list of diameter 2 graphs