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 43 times and downloaded 11 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