کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648876 | 1342434 | 2010 | 13 صفحه PDF | دانلود رایگان |
A card of a graph GG is a subgraph formed by deleting one vertex. The Reconstruction Conjecture states that each graph with at least three vertices is determined by its multiset of cards. A dacard specifies the degree of the deleted vertex along with the card. The degree-associated reconstruction number drn(G)drn(G) is the minimum number of dacards that determine GG. We show that drn(G)=2drn(G)=2 for almost all graphs and determine when drn(G)=1drn(G)=1. For kk-regular nn-vertex graphs, drn(G)≤min{k+2,n−k+1}drn(G)≤min{k+2,n−k+1}. For vertex-transitive graphs (not complete or edgeless), we show that drn(G)≥3drn(G)≥3, give a sufficient condition for equality, and construct examples with large drndrn. Our most difficult result is that drn(G)=2drn(G)=2 for all caterpillars except stars and one 6-vertex example. We conjecture that drn(G)≤2drn(G)≤2 for all but finitely many trees.
Journal: Discrete Mathematics - Volume 310, Issue 20, 28 October 2010, Pages 2600–2612