# zbMATH — the first resource for mathematics

Degree-associated reconstruction number of graphs. (English) Zbl 1219.05093
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.

##### MSC:
 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text:
##### References:
  Asciak, K.J.; Lauri, J., On disconnected graph with large reconstruction number, Ars combin., 62, 173-181, (2002) · Zbl 1074.05509  Bollobás, B., Almost every graph has reconstruction number three, J. graph theory, 14, 1-4, (1990) · Zbl 0702.05061  Bondy, J.A., A graph reconstructor’s manual, (), 221-252 · Zbl 0741.05052  Bondy, J.A.; Hemminger, R.L., Graph reconstruction—a survey, J. graph theory, 1, 227-268, (1977) · Zbl 0375.05040  Harary, F.; Lauri, J., On the class-reconstruction number of trees, Q. J. math. Oxford ser. 2, 39, 47-60, (1988) · Zbl 0655.05049  Harary, F.; Plantholt, M., The graph reconstruction number, J. graph theory, 9, 451-454, (1985) · Zbl 0664.05043  P.J. Kelly, On isometric transformations, Ph.D. Thesis, University of Wisconsin-Madison, 1942.  Kelly, P.J., A congruence theorem for trees, Pacific J. math., 7, 961-968, (1957) · Zbl 0078.37103  Lauri, J., Pseudosimilarity in graphs—a survey, Ars combin., 46, 77-95, (1997) · Zbl 0933.05103  Maccari, A.; Rueda, O.; Viazzi, V., A survey on edge reconstruction of graphs, J. discrete math. sci. cryptogr., 5, 1-11, (2002) · Zbl 1030.05081  McMullen, B.; Radziszowski, S., Graph reconstruction numbers, J. combin. math. combin. comput., 62, 85-96, (2007) · Zbl 1129.05031  Molina, R., Correction of a proof on the ally-reconstruction number of a disconnected graph, Ars combin., 40, 59-64, (1995) · Zbl 0834.05041  W. Myrvold, The ally and adversary reconstruction problems, Ph.D. Thesis, University of Waterloo, 1988.  Myrvold, W., The ally-reconstruction number of a disconnected graph, Ars combin., 28, 123-127, (1989) · Zbl 0704.05036  Myrvold, W., The ally-reconstruction number of a tree with five or more vertices is three, J. graph theory, 14, 149-166, (1990) · Zbl 0704.05037  Myrvold, W., The degree sequence is reconstructible from $$n - 1$$ cards, Discrete math., 102, 2, 187-196, (1992) · Zbl 0759.05065  N. Prince, Personal communication, 2008.  Ramachandran, S., On a new digraph reconstruction conjecture, J. combin. theory ser. B, 31, 143-149, (1981) · Zbl 0474.05053  Ramachandran, S., $$N$$-reconstructibility of nonreconstructible digraphs, Discrete math., 46, 279-294, (1983) · Zbl 0519.05049  Ramachandran, S., Degree associated reconstruction number of graphs and digraphs, Mano. int. J. math. sci., 1, 41-53, (2000)  Ramachandran, S., Reconstruction number for ulam’s conjecture, Ars combin., 78, 289-296, (2006) · Zbl 1164.05413  Ulam, S.M., A collection of mathematical problems, () · Zbl 0086.24101  Welhan, M., Reconstructing trees from two cards, J. graph theory, 33, 243-257, (2009) · Zbl 1201.05065  West, D.B., Introduction to graph theory, (2001), Prentice-Hall
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.