The degree-associated reconstruction number of an unicentroidal tree

Document Type : Research Paper

Authors

Department of Mathematics, Shahid Beheshti University, Tehran, Iran

Abstract

As we know, by deleting one vertex of a graph $G$, we have a subgraph of $G$ called a card of $G$. Also, investigation of that each graph with at least three vertices is determined by its multiset of cards, is called the reconstruction conjecture and the minimum number of dacards that determine $G$ is denoted the degree-associated reconstruction number $drn(G)$. Barrus and West conjectured that $drn(G) \leq 2$ for all but finitely many trees. A tree is unicentroidal or bicentroidal when it has one or two centroids, respectively. An unicentroidal tree $T$ with centroid $v$ is symmetrical if for two neighbours of $u$ and $u'$ of $v$, there exists an automorphism on $T$ mapping $u$ to $u'$. In \cite{Shad}, Shadravan and Borzooei proved that the conjecture is true for any non-symmetrical unicentroidal tree. In this paper, we proved that for any symmetrical unicentroidal tree $T$, $drn(T) \leq 2$. So, we concluded that the conjecture is true for any unicentroidal tree.

Keywords

Main Subjects

References

[1] K. J. Asciak, M. A. Francalanza, J. Lauri and W. Myrvold, A survey of some open questions in reconstruction numbers, Ars Combin., 97 (2010) 443–456.
[2] M. D. Barrus and D. B. West, Degree-associated reconstruction number of graphs, Discrete Math., 310 (2010) 2600–2612.
[3] J. A. Bondy, On Ulam’s conjecture for separable graphs, Pacific J. Math., 31 no. 2 (1969) 281–288.
[4] J. A. Bondy and R. L. Hemminger, Graph reconstruction—a survey, J. Graph Theory, 1 no. 3 (1977) 227–268.
[5] F. Harary and M. Plantholt, The graph reconstruction number, J. Graph Theory, 9 no. 4 (1985) 451–454.
[6] P. J. Kelly, A congruence theorem for trees, Pacific J. Math., 7 (1957) 961–968.
[7] D. G. Kirkpatrick, M. M. Klawe and D. G. Corneil, On pseudosimilarity in trees, J. Combin. Theory Ser. B, 34 no. 3 (1983) 323–339.
[8] S. Monikandan and S. Sundar Raj, Adversary degree associated reconstruction number of graphs, Discrete Math. Algorithms Appl., 7 no. 1 (2015) 16 pp.
[9] S. Ramachandran, Reconstruction number for Ulam’s conjecture, Ars Combin., 78 (2006) 289–296.
[10] M. Shadravan and R. A. Borzooei, On the degree associated reconstruction of unicentroidal tree, Trans. Comb., submitted.
[11] S. M. Ulam, A collection of mathematical problems, Interscience Tracts in Pure and Applied Mathematics, no. 8, Interscience Publishers, New York-London, 1960.

Files

History

  • Receive Date: 20 November 2021
  • Revise Date: 21 September 2023
  • Accept Date: 22 January 2024
  • Published Online: 10 February 2024

Share

How to cite

Statistics