Clique Complex Homology: A Combinatorial Invariant for Chordal Graphs

Clique Complex Homology: A Combinatorial Invariant for Chordal Graphs

Loading document ...
Page
of
Loading page ...

Author(s)

Author(s): Allen D. Parks

Download Full PDF Read Complete Article

630 1086 96-100 Volume 2 - Jul 2013

Abstract

It is shown that a geometric realization of the clique complex of a connected chordal graph is homologically trivial and as a consequence of this it is always the case for any connected chordal graph G that ∑_(k=1)^ω(G)▒(-1)^(k-1) η_k (G)=1, where η_k (G) is the number of cliques of order k in G and ω(G) is the clique number of G.

Keywords

algebraic graph theory, chordal graph, clique complex, hypergraph, homology, Mayer-Vietoris theorem, graph invariant, Euler-Poincaré formula

References

  1. McKee, T.; McMorris, F. Topics in Intersection Graph Theory; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 199
  2. Roberts, F. Discrete Mathematical Models with Application to Social, Biological, and Environmental Problems; Prentice-Hall, Inc.: Englewood Cliffs, NJ, USA, 1976
  3. Brigham, R.; Dutton, R. A compilation of relations between graph invariants. Networks 1985, 15, pp. 73-107.
  4. Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M. On the Desirability of Acyclic Database Schemes. Journal of the Association for Computing Machinery 1983, 30, pp. 479-513
  5. Fagin, R. Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. Journal of the Association for Computing Machinery 1983, 30, pp. 514-550
  6. Hocking, J.; Young, G. Topology; Addison-Wesley: Reading, MA, USA, 1961; p. 242
  7. Munkres, J. Elements of Algebraic Topology; Addison-Wesley: Reading, MA, USA, 1984; p. 142
  8. Rotman, J. An Introduction to the Theory of Groups; Allyn and Bacon, Boston, MA, USA, 1984; p. 254
  9. D’Atri, A.; Moscarini, M. On Hypergraph Acyclicity and Graph Chordality. Information Processing Letters 1988, 29, pp.271-274

Cite this Article:

  • BibTex
  • RIS
  • APA
  • Harvard
  • IEEE
  • MLA
  • Vancouver
  • Chicago

International Journal of Sciences is Open Access Journal.
This article is licensed under a Creative Commons Attribution 4.0 International (CC BY 4.0) License.
Author(s) retain the copyrights of this article, though, publication rights are with Alkhaer Publications.

Search Articles

Issue April 2019

Volume 8, April 2019


Table of Contents


Order Print Copy

World-wide Delivery is FREE

Share this Issue with Friends:


Submit your Paper