کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430558 | 688041 | 2013 | 7 صفحه PDF | دانلود رایگان |

An edge-deleted subgraph of a graph G is called an ecard of G. An ecard of G with which the degree of the deleted edge is also given is called a degree associated ecard (or da-ecard) of G. The edeck (da-edeck) of a graph G is its collection of ecards (da-ecards). The degree associated edge reconstruction number , dern(G)dern(G), of a graph G is the size of the smallest collection of ecards of G that uniquely determines G. The adversary degree associated edge reconstruction number , adern(G)adern(G), of a graph G is the minimum number k such that every collection of k da-ecards of G uniquely determines G . In this paper, we prove that dern(G)=adern(G)=1dern(G)=adern(G)=1 for any regular graph G. We also prove that if G is a graph obtained from K1,mK1,m by subdividing each edge at most once, then dern(G)⩽2dern(G)⩽2 and adern(G)⩽4adern(G)⩽4. We also determine these parameters for several product graphs.
Journal: Journal of Discrete Algorithms - Volume 23, November 2013, Pages 35–41