Clique Complex Homology: A Combinatorial Invariant for Chordal Graphs

Author(s): Allen D. Parks

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.

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

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