Abstract
A vertex-deleted subgraph of a graph G is called a card of G. A card of G with which the degree of the deleted vertex is also given is called a degree associated card (or dacard) of G. The degree associated reconstruction number of a graph G (or drn(G)) is the size of the smallest collection of dacards of G that uniquely determines G. It is shown that \(drn(G)=1~\text {or}~2\) for all biregular bipartite graphs with degrees d and \(d+k\), \(k\ge 2\) except the bistar \(B_{2,2}\) on 6 vertices and that \(drn(B_{2,2})=3\).
S. Monikandan—Research is supported by the SERB, Govt. of India, Grant no. EMR/2016/000157.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anu, A., Monikandan, S.: Degree associated reconstruction number of certain connected graphs with unique end vertex and a vertex of degree \(n-2\). Discrete Math. Algorithms Appl. 8(4), 1650068-1–1650068-13 (2016)
Anusha Devi, P., Monikandan, S.: Degree associated reconstruction number of graphs with regular pruned graph. Ars Combin. (to appear)
Anusha Devi, P., Monikandan, S.: Degree associated reconstruction number of connected digraphs with unique end vertex. Australas. J. Combin. 66(3), 365–377 (2016)
Asciak, K.J., Francalanza, M.A., Lauri, J., Myrvold, W.: A survey of some open questions in reconstruction numbers. Ars Combin. 97, 443–456 (2010)
Barrus, M.D., West, D.B.: Degree-associated reconstruction number of graphs. Discrete Math. 310, 2600–2612 (2010)
Bondy, J.A.: A graph reconstructors manual, in Surveys in Combinatorics. In: Proceedings of 13th British Combinatorial Conference London Mathematical Society, Lecture Note Series, vol. 166, pp. 221–252 (1991)
Harary, F.: Graph Theory. Addison Wesley, Reading (1969)
Harary, F.: On the reconstruction of a graph from a collection of subgraphs. In: Fieldler, M. (ed.) Theory of Graphs and its Applications, pp. 47–52. Academic Press, New York (1964)
Harary, F., Plantholt, M.: The graph reconstruction number. J. Graph Theory 9, 451–454 (1985)
Kelly, P.J.: On isometric transformations. Ph.D. Thesis, University of Wisconsin Madison (1942)
Ma, M., Shi, H., Spinoza, H., West, D.B.: Degree-associated reconstruction parameters of complete multipartite graphs and their complements. Taiwanese J. Math. 19(4), 1271–1284 (2015)
Ramachandran, S.: On a new digraph reconstruction conjecture. J. Combin. Theory Ser. B. 31, 143–149 (1981)
Ramachandran, S.: Degree associated reconstruction number of graphs and digraphs. Mano. Int. J. Math. Scis. 1, 41–53 (2000)
Spinoza, H.: Degree-associated reconstruction parameters of some families of trees (2014). (submitted)
Stockmeyer, P.K.: The falsity of the reconstruction conjecture for tournaments. J. Graph Theory. 1, 19–25 (1977)
Ulam, S.M.: A Collection of Mathematical Problems. Interscience Tracts in Pure and Applied Mathematics 8. Interscience Publishers, New York (1960)
Acknowledgments
The work reported here is supported by the Research Project EMR/2016/000157 awarded to the second author by SERB, Government of India, New Delhi.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Anu, A., Monikandan, S. (2017). Degree Associated Reconstruction Number of Biregular Bipartite Graphs Whose Degrees Differ by at Least Two. In: Arumugam, S., Bagga, J., Beineke, L., Panda, B. (eds) Theoretical Computer Science and Discrete Mathematics. ICTCSDM 2016. Lecture Notes in Computer Science(), vol 10398. Springer, Cham. https://doi.org/10.1007/978-3-319-64419-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-64419-6_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-64418-9
Online ISBN: 978-3-319-64419-6
eBook Packages: Computer ScienceComputer Science (R0)