[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Generalisations of Hypomorphisms and Reconstruction of Hypergraphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We define certain generalisations of hypergraph hypomorphisms, which we call k-morphisms, \((k,n-k)\)-hypomorphisms, partial \((k,n-k)\)-hypomorphisms. They are special bijections between collections of k-subsets of vertex sets of hypergraphs. We show that these mappings lead to alternative representations of the automorphism groups of r-uniform hypergraphs and vertex stabilisers of graphs. We also use them to show that almost every r-uniform hypergraph is reconstructible and \((k,n-k)\)-reconstructible. As a consequence we also obtain the result that almost every r-uniform hypergraph is asymmetric.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Bollobás, B.: Almost every graph has reconstruction number 3. J. Graph Theory 14, 1–4 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  2. Chinn, P.Z.: A graph with \(p\) order subgraphs is reconstructible. In: Capobianco M. et al. (eds.) Recent Trends in Graph Theory, vol. 186 of Lecture Notes in Mathematics, pp. 71-73. Springer-Verlag (1971)

  3. Czimmermann, P.: The \((k, n-k)\)-reconstruction of graphs. Studies of the University of Žilina 19,1–8 (2005)

  4. Czimmermannová, O.: An introduction to the \((k, n-k)\)-reconstruction of hypergraphs. J. Inf. Control Manag. Syst. 7(1), 21–24 (2009)

    Google Scholar 

  5. Erdös, P., Rényi, A.: Asymmetric graphs. Acta Math. Acad. Sci. Hungar. 11, 295–315 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  6. Hashiguchi, K.: The Double Reconstruction Conjectures about Colored Hypergraphs and Colored Directed Graphs, in Latin 92, vol. 583 of Lecture Notes in Computer Science. pp. 246–261. Springer-Verlag, ISBN 3-540-55284-7 (1992)

  7. Hashiguchi, K.: The Double Reconstruction Conjecture about Finite Colored Hypergraphs. J. Comb. Theory Ser. B 54(1), 64–76 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kocay, W.L.: A family of non-reconstructible hypergraphs. J. Comb. Theory Ser. B 42(1), 46–63 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  9. Korshunov, A.D.: Number of nonisomorphic graphs in an \(n\)-point graph. Math. Notes Acad. USSR 9, 155–160 (1971)

    Article  MATH  Google Scholar 

  10. Lauri, J., Scapellato, R.: Topics in graph automorphisms and reconstruction. Cambridge University Press, Cambridge (2003)

    MATH  Google Scholar 

  11. Müller, V.: Probabilistic reconstruction from subgraphs. Commen. Math. Univ. Carolinae 17, 709–719 (1976)

    MathSciNet  MATH  Google Scholar 

  12. Ramachandran, S.: On a New Digraph Reconstruction Conjecture. J. Comb. Theory Ser. B 31(2), 143–149 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  13. Stockmeyer, P.: The falsity of the reconstruction conjecture for tournaments. J. Graph Theory 1, 19–25 (1977)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Žilina, Zilina, Slovakia

    Peter Czimmermann

Authors
  1. Peter Czimmermann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Peter Czimmermann.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Czimmermann, P. Generalisations of Hypomorphisms and Reconstruction of Hypergraphs. Graphs and Combinatorics 32, 887–901 (2016). https://doi.org/10.1007/s00373-015-1639-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-015-1639-x

Keywords

Search

Navigation