Abstract
The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bollobás, B.: Almost every graph has reconstruction number three. Journal of Graph Theory 14, 1–4 (1990)
Bondy, J.A.: On Ulam’s conjecture for separable graphs. Pacific Journal of Mathematics 31, 281–288 (1969)
Bondy, J.A.: A graph reconstructor’s manual. In: Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 166, pp. 221–252 (1991)
Even, S.: Algorithmic Combinatorics. Macmillan, New York (1973)
Giles, W.B.: The reconstruction of outerplanar graphs. Journal of Combinatorial Theory, Series B 16, 215–226 (1974)
Greenwell, D.L., Hemminger, R.L.: Reconstructing the n-connected components of a graph. Aequationes Mathematicae 9, 19–22 (1973)
Harary, F.: A survey of the reconstruction conjecture. In: Graphs and Combinatorics. Lecture Notes in Mathematics, vol. 406, pp. 18–28 (1974)
Hell, P., Huang, J.: Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs. SIAM Journal on Discrete Mathematics 18, 554–570 (2005)
Kelly, P.J.: A congruence theorem for trees. Pacific Journal of Mathematics 7, 961–968 (1957)
Manvel, B.: Reconstruction of unicyclic graphs. In: Proof Techniques in Graph Theory. Academic Press, New York (1969)
McKay, B.D.: Small graphs are reconstructible. Australasian Journal of Combinatorics 15, 123–126 (1997)
von Rimscha, M.: Reconstructibility and perfect graphs. Discrete Mathematics 47, 283–291 (1983)
Saitoh, T., Otachi, Y., Yamanaka, K., Uehara, R.: Random generation and enumeration of bipartite permutation graphs. In: Zaroliagis, C. (ed.) ISAAC 2009. LNCS, vol. 5868, pp. 1104–1113. Springer, Heidelberg (2009)
Tutte, W.T.: On dichromatic polynomials. Journal of Combinatorial Theory 2, 310–320 (1967)
Tutte, W.T.: All king’s horses. A guide to reconstruction. In: Graph Theory and Related Topics, pp. 15–33. Academic Press, New York (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kiyomi, M., Saitoh, T., Uehara, R. (2010). Bipartite Permutation Graphs Are Reconstructible. In: Wu, W., Daescu, O. (eds) Combinatorial Optimization and Applications. COCOA 2010. Lecture Notes in Computer Science, vol 6509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17461-2_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-17461-2_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17460-5
Online ISBN: 978-3-642-17461-2
eBook Packages: Computer ScienceComputer Science (R0)