Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Existential Closure in Line Graphs

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

Abstract

A graph is n-existentially closed if, for all disjoint sets of vertices A and B with \(|A\cup B|=n\), there is a vertex z not in \(A\cup B\) adjacent to each vertex of A and to no vertex of B. In this paper, we investigate n-existentially closed line graphs. In particular, we present necessary conditions for the existence of such graphs as well as constructions for finding infinite families of such graphs. We also prove that there are exactly five 2-existentially closed planar line graphs. We then consider the existential closure of the line graphs of hypergraphs and present constructions for 2-existentially closed line graphs of hypergraphs.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Beineke, L.W.: Characterizations of derived graphs. J. Combin. Theory 9, 129–135 (1970)

    Article  MathSciNet  Google Scholar 

  2. Blass, A., Exoo, G., Harary, F.: Paley graphs satisfy all first-order adjacency axioms. J. Graph Theory 5(4), 435–439 (1981)

    Article  MathSciNet  Google Scholar 

  3. Bollobás, B., Thomason, A.: Graphs which contain all small graphs. Eur. J. Combin. 2(1), 13–15 (1981)

    Article  MathSciNet  Google Scholar 

  4. Bonato, A.: The search for \(n\)-e.c. graphs. Contrib. Discrete Math. 4(1), 40–53 (2009)

    MathSciNet  Google Scholar 

  5. Bonato, A., Cameron, K.: On an adjacency property of almost all graphs. Discrete Math. 231, 103–119 (2001)

    Article  MathSciNet  Google Scholar 

  6. Brinkmann, G., McKay, B.D.: Fast generation of planar graphs. MATCH Commun. Math. Comput. Chem. 58(2), 323–357 (2007)

    MathSciNet  Google Scholar 

  7. Dhanalakshmi, S., Sadagopan, N., Manogna, V.: On \(2K_2\)-free graphs. Int. J. Pure Appl. Math. 109(7), 167–173 (2016)

    Google Scholar 

  8. Fellows, M., Hell, P., Seyffarth, K.: Large planar graphs with given diameter and maximum degree. Discrete Appl. Math. 61(2), 133–153 (1995)

    Article  MathSciNet  Google Scholar 

  9. Forbes, A.D., Grannell, M.J., Griggs, T.S.: Steiner triple systems and existentially closed graphs. Electron. J. Combin. 12, #R42 (2005)

  10. Fulek, R., Morić, F., Pritchard, D.: Diameter bounds for planar graphs. Discrete Math. 311(5), 327–335 (2011)

    Article  MathSciNet  Google Scholar 

  11. Hell, P., Seyffarth, K.: Largest planar graphs of diameter two and fixed maximum degree. Graph theory and combinatorics (Marseille-Luminy, 1990). Discrete Math. 111(1–3), 313–322 (1993)

    Article  MathSciNet  Google Scholar 

  12. Hermes, O.: Die Formen der Vielflache. J. Reine Angew. Math. [I] 120, 27–59 (1899). ([II], v. 120, (1899) 305–353, plate 1; [III], v. 122, (1900) 124–154, plates 1, 2; [IV], v. 123, (1901) 312–342, plate 1)

    MathSciNet  Google Scholar 

  13. Horsley, D., Pike, D.A., Sanaei, A.: Existential closure of block intersection graphs of infinite designs having infinite block size. J. Comb. Des. 19, 317–327 (2011)

    Article  MathSciNet  Google Scholar 

  14. Johnson, N.W.: Convex polyhedra with regular faces. Can. J. Math. 18, 169–200 (1966)

    Article  MathSciNet  Google Scholar 

  15. Kirkman, T.P.: Application of the theory of the polyhedra to the enumeration and registration of results. Proc. R. Soc. Lond. 12, 341–380 (1862–1863)

  16. McKay, N.A., Pike, D.A.: Existentially closed BIBD block-intersection graphs. Electron. J. Combin. 14, #R70 (2007)

  17. Meister, D.: Two characterisations of minimal triangulations of \(2K_2\)-free graphs. Discrete Math. 306(24), 3327–3333 (2006)

    Article  MathSciNet  Google Scholar 

  18. Pike, D.A., Sanaei, A.: Existential closure of block intersection graphs of infinite designs having finite block size and index. J. Combin. Des. 19, 85–94 (2011)

    Article  MathSciNet  Google Scholar 

  19. Read, R., Wilson, R.: An Atlas of Graphs. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York (1998)

    Book  Google Scholar 

  20. Wagner, K.: Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114, 570–590 (1937)

    Article  MathSciNet  Google Scholar 

Download references

Funding

This work was funded by Natural Sciences and Engineering Research Council of Canada to Andrea C. Burgess with Grant number RGPIN-2019-04328 and to David A. Pike with Grant number RGPIN-2022-03829.

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, University of New Brunswick, Saint John, NB, E2L 4L5, Canada

    Andrea C. Burgess

  2. Department of Mathematics and Statistics, Memorial University of Newfoundland, St. John’s, NL, A1C 5S7, Canada

    Robert D. Luther & David A. Pike

Authors
  1. Andrea C. Burgess
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert D. Luther
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David A. Pike
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robert D. Luther.

Ethics declarations

Conflict of interest

The authors have no relevant financial or non-financial interests to disclose. Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Burgess, A.C., Luther, R.D. & Pike, D.A. Existential Closure in Line Graphs. Graphs and Combinatorics 40, 101 (2024). https://doi.org/10.1007/s00373-024-02829-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-024-02829-x

Keywords

Mathematics Subject Classification

Search

Navigation