On $l$-reconstructibility of degree list of graphs

Document Type : Original Article

Authors

Department of 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 \leq i \leq 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 \leq i \leq n-3$, where $l \geq 4$ and $n \geq l+6$, the degree list of the graph is determined.

Keywords

References

[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.
AUT Journal of Mathematics and Computing
Volume 5, Issue 1
2024
Pages 39-44

Files

Share

How to cite

Statistics