Original Research Article
Article volume = 2022 and issue = 1
Pages: 11–14
Article publication Date: November 21, 2022
You can download PDF file of the article here: Download
Visited 267 times and downloaded 103 times
On Rational Clique Roots of Maximal Outerplanar Graphs
Hossein Teimoori Faal
Department of Computer Science, Faculty of Mathematical and Computer Sciences, Allameh Tabatabai University, Tehran, Iran
Abstract:
The ordinary generating function of the number of complete subgraphs of a simple graph G is called the clique polynomial of G. A real root of a clique polynomial of a graph G is called a clique root of G. In this paper, we prove that the class of maximal outerplanar garphs has only rational clique roots. In particular, we show that maximal outerplanar graphs have a clique root r=-1 of multiplicity two. We also disuss about some possible extensions of our results to the class of maximal planar graphs. We finally conclude the paper with some interesting open questions and conjectures.
Keywords:
Maximal outerplanar graphs, clique polynomial, triangulated graphs, Apollonian networks, clique roots.
References:
- [1] F. Brenti, Unimodal, Log-concave and Polya Frequency Sequences, Mem. Amer. Math. Soc, (1989). 1
- [2] H. Hajiabolhassan, M. L. Mehrabadi, On Clique Polynomials, Australasian Journal of Combinatorics, 18 (1998), 313-316. 1, 1, 2
- [3] J. A. Bondy, U. S. R. Murty, Graph Theory, 2nd ed., Springer-Verlag, (2008). 1
- [4] R. C. Laskar, H. M. Mulder, B. Novick, Maximal Outerplanar Graphs as Chordal Graphs, Path-neighborhood Graphs, and Triangle Graphs, Australasian Journal of Combinatorics., 52 (2012), 185-195. 2, 2
- [5] P. Haxell, A. Kostochka, S. Thomassé, Packing and Covering Triangles in K4-free Planar Graphs, Graphs and Combinatorics., 28 (2012), 653-662. 3.4
Cite this article as:
- Hossein Teimoori Faal, On Rational Clique Roots of Maximal Outerplanar Graphs, Communications in Combinatorics, Cryptography & Computer Science, 2022(1), PP.11–14, 2022
- Export citation to BibTeX