Observations Concerning Chordal Graph Polynomials

Author(s): Allen D. Parks

For every graph that is clique equivalent to a connected chordal graph, it is shown that the associated dependence polynomial has a unit root and that the associated clique and independence polynomials have negative unit roots. The dependence polynomial for a graph that is the join of two graphs is also shown to have a unit root when at least one of the two joined graphs is clique equivalent to a connected chordal graph. A condition satisfied by the eigenvalues of graphs that are clique equivalent to connected chordal graphs with clique numbers less than four is identified.

chordal graph, graph polynomial, dependence polynomial, clique polynomial, independence polynomial, graph eigenvalues

1. McKee, T.; McMorris, F. Topics in Intersection Graph Theory; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 1999
2. Roberts, F. Discrete Mathematical Models with Application to Social, Biological, and Environmental Problems; Prentice-Hall, Inc.: Englewood Cliffs, NJ, USA, 1976
3. Fisher, D.; Solow, A. Dependence Polynomials Discrete Mathematics 1990, 82, pp. 251-258
4. Goldwurm, M.; Saporiti, L. Clique polynomials and trace monoids Rapporto Interno n.222-98 Departimento di Scienze dell’Informazione; Universitá degli Studi di Milano, Milano, Italy, 1998
5. Hajiabolhassan, H.; Mehrabadi, M. On clique polynomials Australasian Journal of Combinatorics 1998, 18, pp. 313-316
6. Brown, J.; Hickman, C.; Nowakowski, R. The independence fractal of a graph Journal of Combinatorial Theory, Series B 2003, 87, pp. 209-230
7. Levit, V.; Mandrescu, E. The independence polynomial of a graph-a survey Proceedings of the 1st International Conference on Algebraic Informatics 2005, 233254
8. Rosenfeld, V. The independence polynomial of rooted products of graphs Discrete Applied Mathematics 2010, 158, pp. 551-558