کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430851 | 688203 | 2015 | 10 صفحه PDF | دانلود رایگان |
A vertex-deleted subgraph of a graph G is a card. A dacard specifies the degree of the deleted vertex along with the card. The adversary degree-associated reconstruction number adrn(G)adrn(G) is the least k such that every set of k dacards determines G . We determine adrn(Dm,n,p)adrn(Dm,n,p), where the double-broom Dm,n,pDm,n,p with p≥2p≥2 is the tree with m+n+pm+n+p vertices obtained from a path with p vertices by appending m leaves at one end and n leaves at the other end. We determine adrn(Dm,n,p)adrn(Dm,n,p) for all m,n,pm,n,p. For 2≤m≤n2≤m≤n, usually adrn(Dm,n,p)=m+2adrn(Dm,n,p)=m+2, except adrn(Dm,m+1,p)=m+1adrn(Dm,m+1,p)=m+1 and adrn(Dm,m+2,p)=m+3adrn(Dm,m+2,p)=m+3. There are exceptions when (m,n)=(2,3)(m,n)=(2,3) or p=4p=4. For m=1m=1 the usual value is 4, with exceptions when p∈{2,3}p∈{2,3} or n=2n=2.
Journal: Journal of Discrete Algorithms - Volume 33, July 2015, Pages 150–159