Document Type : Original Article

**Authors**

Mathematics, Shahid Beheshti University, Tehran, Iran

**Abstract**

The *k*-deck of a graph is the multiset of its subgraphs induced by *k *vertices which is denoted by *D*_{k}(*G*). A graph or graph property is *l*-reconstructible if it is determined by the deck of subgraphs obtained by deleting *l *vertices. Manvel proved that from the (*n*−*l*)-deck of a graph and the numbers of vertices with degree *i *for all *i*, *n*−*l *≤ *i *≤ *n*−1, the degree list of the graph is determined. In this paper, we extend this result and prove that if *G *is a graph with *n *vertices, then from the (*n*−*l*)-deck of *G *and the numbers of vertices with degree *i *for all *i*, *n*−*l *≤ *i *≤ *n*−3, where *l *≥ 4 and *n *≥ *l *+ 6, the degree list of the graph is determined

**Keywords**

[1] B. Bollobas´ , Almost every graph has reconstruction number three, J. Graph Theory, 14 (1990), pp. 1–4.

[2] J. A. Bondy and R. L. Hemminger, Graph reconstruction—a survey, J. Graph Theory, 1 (1977), pp. 227– 268. [3] Z. A. Chernyak, Some additions to an article by B. Manvel: “Some basic observations on Kelly’s conjecture for graphs”, (Russian) Vests¯ı Akad. Navuk BSSR Ser. F¯ız.-Mat. Navuk, 126 (1982), pp. 44–49.

[4] P. J. Kelly, ON ISOMETRIC TRANSFORMATIONS, ProQuest LLC, Ann Arbor, MI, 1942. Thesis (Ph.D.)– The University of Wisconsin - Madison.

[5] P. J. Kelly, A congruence theorem for trees, Pacific J. Math., 7 (1957), pp. 961–968.

[6] A. V. Kostochka, M. Nahvi, D. B. West, and D. Zirlin, Degree lists and connectedness are 3- reconstructible for graphs with at least seven vertices, Graphs Combin., 36 (2020), pp. 491–501.

[7] , 3-regular graphs are 2-reconstructible, European J. Combin., 91 (2021), Paper No. 103216, 10.

[8] A. V. Kostochka and D. B. West, On reconstruction of graphs from the multiset of subgraphs obtained by deleting ℓ vertices, IEEE Trans. Inf. Theory, 67 (2021), pp. 3278–3286.

[9] A. Maccari, O. Rueda, and V. Viazzi, A survey on edge reconstruction of graphs, J. Discrete Math. Sci. Cryptography, 5 (2002), pp. 1–11.

[10] B. Manvel, Some basic observations on Kelly’s conjecture for graphs, Discrete Math., 8 (1974), pp. 181–185.

[11] D. Rivshin and S. a. P. Radziszowski, Multi-vertex deletion graph reconstruction numbers, J. Combin. Math. Combin. Comput., 78 (2011), pp. 303–321.

[12] H. Spinoza and D. B. West, Reconstruction from the deck of k-vertex induced subgraphs, J. Graph Theory, 90 (2019), pp. 497–522.

[13] R. Taylor, Reconstructing degree sequences from k-vertex-deleted subgraphs, Discrete Math., 79 (1990), pp. 207–213.

[14] S. M. Ulam, A collection of mathematical problems, Interscience Tracts in Pure and Applied Mathematics, no. 8, Interscience Publishers, New York-London, 1960.

January 2024

Pages 39-44