×

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.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Asciak, K.J.; Lauri, J., On disconnected graph with large reconstruction number, Ars combin., 62, 173-181, (2002) · Zbl 1074.05509
[2] Bollobás, B., Almost every graph has reconstruction number three, J. graph theory, 14, 1-4, (1990) · Zbl 0702.05061
[3] Bondy, J.A., A graph reconstructor’s manual, (), 221-252 · Zbl 0741.05052
[4] Bondy, J.A.; Hemminger, R.L., Graph reconstruction—a survey, J. graph theory, 1, 227-268, (1977) · Zbl 0375.05040
[5] Harary, F.; Lauri, J., On the class-reconstruction number of trees, Q. J. math. Oxford ser. 2, 39, 47-60, (1988) · Zbl 0655.05049
[6] Harary, F.; Plantholt, M., The graph reconstruction number, J. graph theory, 9, 451-454, (1985) · Zbl 0664.05043
[7] P.J. Kelly, On isometric transformations, Ph.D. Thesis, University of Wisconsin-Madison, 1942.
[8] Kelly, P.J., A congruence theorem for trees, Pacific J. math., 7, 961-968, (1957) · Zbl 0078.37103
[9] Lauri, J., Pseudosimilarity in graphs—a survey, Ars combin., 46, 77-95, (1997) · Zbl 0933.05103
[10] 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
[11] McMullen, B.; Radziszowski, S., Graph reconstruction numbers, J. combin. math. combin. comput., 62, 85-96, (2007) · Zbl 1129.05031
[12] Molina, R., Correction of a proof on the ally-reconstruction number of a disconnected graph, Ars combin., 40, 59-64, (1995) · Zbl 0834.05041
[13] W. Myrvold, The ally and adversary reconstruction problems, Ph.D. Thesis, University of Waterloo, 1988.
[14] Myrvold, W., The ally-reconstruction number of a disconnected graph, Ars combin., 28, 123-127, (1989) · Zbl 0704.05036
[15] 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
[16] Myrvold, W., The degree sequence is reconstructible from \(n - 1\) cards, Discrete math., 102, 2, 187-196, (1992) · Zbl 0759.05065
[17] N. Prince, Personal communication, 2008.
[18] Ramachandran, S., On a new digraph reconstruction conjecture, J. combin. theory ser. B, 31, 143-149, (1981) · Zbl 0474.05053
[19] Ramachandran, S., \(N\)-reconstructibility of nonreconstructible digraphs, Discrete math., 46, 279-294, (1983) · Zbl 0519.05049
[20] Ramachandran, S., Degree associated reconstruction number of graphs and digraphs, Mano. int. J. math. sci., 1, 41-53, (2000)
[21] Ramachandran, S., Reconstruction number for ulam’s conjecture, Ars combin., 78, 289-296, (2006) · Zbl 1164.05413
[22] Ulam, S.M., A collection of mathematical problems, () · Zbl 0086.24101
[23] Welhan, M., Reconstructing trees from two cards, J. graph theory, 33, 243-257, (2009) · Zbl 1201.05065
[24] 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.