Nearly all Biregular Graphs have Degree Associated Edge Reconstruction Number at most Three

摘要

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. It is shown that dern(G) <= 4 for all biregular graphs G with degrees d and d + i (i >= 1) except the graphs with a vertex of degree d + 1 adjacent to at least two vertices of degree d; in fact, the dern(G) attains its bound only for the biregular graphs mK(1,3) (m >= 2).