The degree associated edge reconstruction number of bidegreed graphs is at most four

Abstract

The degree of an edge \(uv\) of a graph \(G\) is \(d_G(u)+d_G(v)-2.\) The degree associated edge reconstruction number of a graph \(G\) (or dern(G)) is the minimum number of degree associated edge-deleted subgraphs that uniquely determines \(G.\) Graphs whose vertices all have one of two possible degrees \(d\) and \(d+1\) are called \((d,d+1)\)-bidegreed graphs. It was proved, in a sequence of two papers [1,17], that \(dern(mK_{1,3})=4\) for \(m>1,\) \(dern(mK_{2,3})=dern(rP_3)=3\) for \(m>0, ~r>1\) and \(dern(G)=1\) or \(2\) for all other bidegreed graphs \(G\) except the \((d,d+1)\)-bidegreed graphs in which a vertex of degree \(d+1\) is adjacent to at least two vertices of degree \(d.\) In this paper, we prove that \(dern(G)= 1\) or \(2\) for this exceptional bidegreed graphs \(G.\) Thus, \(dern(G)\leq 4\) for all bidegreed graphs \(G.\)