2021/12/17 by Hossein Teimoori Faal, Faal, Hossein Teimoori
Mathematics · Chemistry · #Graph theory and applications #Advanced Combinatorial Mathematics #Synthesis and Properties of Aromatic Compounds
paper · pdf · doi:10.48550/arxiv.2112.09721
A complete subgraph of a given graph is called a clique. A clique Polynomial of a graph is a generating function of the number of cliques in G. A real root of the clique polynomial of a graph G is called a clique root of G. Hajiabolhassan and Mehrabadi showed that the clique polynomial of any simple graph has a clique root in [-1,0). As a generalization of their result, the author of this paper showed that the class of K4-free connected chordal graphs has also only clique roots. A given graph G is called flat if each edge of G belongs to at most two triangles of G. In answering the author's open question about the class of non-chordal graphs with the same property of having only c;ique roots, we extend the aforementioned result to the class of K4-free flat graphs. In particular, we prove that the class of K4-free flat graphs without isolated edges has r=-1 as one of its clique roots. We finally present some interesting open questions and conjectures regarding clique roots of graphs.