History


Please fill in your query. A complete syntax description you will find on the General Help page.
Degree-associated reconstruction number of graphs. (English)
Discrete Math. 310, No. 20, 2600-2612 (2010).
Summary: A card of a graph $G$ 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$) is the minimum number of dacards that determine $G$. We show that drn($G)=2$ for almost all graphs and determine when drn($G)=1$. For $k$-regular $n$-vertex graphs, drn($G)\leq \min \{ k+2,n - k+1 \}$. For vertex-transitive graphs (not complete or edgeless), we show that drn($G)\geq 3$, give a sufficient condition for equality, and construct examples with large drn. Our most difficult result is that drn($G)=2$ for all caterpillars except stars and one 6-vertex example. We conjecture that drn($G)\leq 2$ for all but finitely many trees.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!