Article ID Journal Published Year Pages File Type
430558 Journal of Discrete Algorithms 2013 7 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,