2019•Electronic Journal of Graph Theory and ApplicationsOpen access

Clique roots of K4-free chordal graphs

Hossein Teimoori Faal

Open full text 2 citations

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 K 4 -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.

Open-access reader

About this research paper

What this paper is about

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 K 4 -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.

Why it matters

OpenAlex reports 2 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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 K 4 -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.

Key concepts: Combinatorics, Chordal graph, Mathematics, Split graph, Block graph, Clique, Discrete mathematics, Clique graph

Related papers

Back to paper searchBrowse research topicsOriginal source
Clique roots of K4-free chordal graphs — Research Paper | ScholarLens