Clique roots of K4-free chordal graphs

Hossein Teimoori Faal

Abstract


The clique polynomial C(G, x) of a finite, simple and undirected graph G = (V, E) is defined as the ordinary generating function of the number of complete subgraphs of G. A real root of C(G, x) is called a clique root of the graph G. Hajiabolhasan and Mehrabadi showed that every simple graph G has at least a clique root in the interval [ − 1, 0). Moreover, they showed that the class of triangle-free graphs has only clique roots. In this paper, we extend their result by showing that the class of K4-free chordal graphs has also only clique roots. In particular, we show that this class has always a clique root  − 1. We conclude our paper with some interesting open questions and conjectures.


Keywords


clique polynomial, clique root, chordal graph, clique decomposition

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.1.8

Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats