Skip to main content
SpringerLink
Log in

Four-Cycled Graphs with Topological Applications

  • Published:
Annals of Combinatorics Aims and scope Submit manuscript

Abstract

We call a simple graph G a 4-cycled graph if either it has no edges or every edge of it is contained in an induced 4-cycle of G. Our interest on 4-cycled graphs is motivated by the fact that their clique complexes play an important role in the simple-homotopy theory of simplicial complexes. We prove that the minimal simple models within the category of flag simplicial complexes are exactly the clique complexes of some 4-cycled graphs. We further provide structural properties of 4-cycled graphs and describe constructions yielding such graphs. We characterize 4-cycled cographs, and 4-cycled graphs arising from finite chessboards. We introduce a family of inductively constructed graphs, the external extensions, related to an arbitrary graph, and determine the homotopy type of the independence complexes of external extensions of some graphs.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Barmak J.A., Minian E.G.: Minimal finite models. J. Homotopy Relat. Struct. 2(1), 127–140 (2007)

    MathSciNet  MATH  Google Scholar 

  2. Barmak J.A., Minian E.G.: Simple homotopy types and finite spaces. Adv. Math. 218(1), 87–104 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  3. Boulet R., Fieux E., Jouve B.: Simplicial simple homotopy of flag complexes in terms of graphs. European J. Combin. 31(1), 161–176 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Brandstädt, A., Le, B.V., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1999)

  5. Cohen M.M.: A Course in Simple-Homotopy Theory. Springer-Verlag, New York (1973)

    MATH  Google Scholar 

  6. Corneil D.G., Lerchs H., Burlingham L.S.: Complement reducible graphs. Discrete Appl. Math., 3(3), 163–174 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dochtermann, A., Engström, A.: Algebraic properties of edge ideals via combinatorial topology. Electronic J. Combin. 16(2), #R2 (2009)

  8. Ehrenborg R., Hetyei G.: The topology of the independence complex. European J. Combin. 27(6), 906–923 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Hatcher A.: Algebraic Topology. Cambridge University Press, Cambridge (2001)

    Google Scholar 

  10. Kozlov D.: Combinatorial Algebraic Topology. Springer, Berlin (2008)

    Book  MATH  Google Scholar 

  11. Marietti M., Testa D.: Cores of simplicial complexes. Discrete Comput. Geom. 40(3), 444–468 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  12. Lovász L.: Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25(3), 319–324 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  13. Villarreal R.H.: Cohen-Macaulay graphs. Manuscripta Math. 66(3), 277–293 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  14. Wachs M.L.: Topology of matching, chessboard, and general bounded degree graph complexes. Algebra Universalis 49(4), 345–385 (2003)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Işik University, Şile, Istanbul, 34980, Turkey

    Türker Bıyıkoğlu

  2. Department of Mathematics, Suleyman Demirel University, Isparta, 32260, Turkey

    Yusuf Civan

Authors
  1. Türker Bıyıkoğlu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yusuf Civan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Türker Bıyıkoğlu.

Additional information

Both authors are supported by TÜBA through Young Scientist Award Program (TÜBA-GEBIİP/2009-06 and 2008-08).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bıyıkoğlu, T., Civan, Y. Four-Cycled Graphs with Topological Applications. Ann. Comb. 16, 37–56 (2012). https://doi.org/10.1007/s00026-011-0120-7

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00026-011-0120-7

Mathematics Subject Classification

Keywords

Search

Navigation