Degree-associated reconstruction number of graphs |
| |
Authors: | Michael D Barrus |
| |
Institution: | a Department of Mathematics, Black Hills State University, Spearfish, SD 61801, United States b Department of Mathematics, University of Illinois, Urbana, IL 61801, United States |
| |
Abstract: | 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)≤min{k+2,n−k+1}. For vertex-transitive graphs (not complete or edgeless), we show that drn(G)≥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)≤2 for all but finitely many trees. |
| |
Keywords: | Reconstruction conjecture Reconstruction number Vertex-transitive graph Tree Caterpillar |
本文献已被 ScienceDirect 等数据库收录! |
|