Observations Concerning Chordal Graph Polynomials

Observations Concerning Chordal Graph Polynomials

Loading document ...
Page
of
Loading page ...

Author(s)

Author(s): Allen D. Parks

Download Full PDF Read Complete Article

416 1114 36-39 Volume 4 - Jan 2015

Abstract

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.

Keywords

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

References

  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

Cite this Article:

International Journal of Sciences is Open Access Journal.
This article is licensed under a Creative Commons Attribution 4.0 International (CC BY 4.0) License.
Author(s) retain the copyrights of this article, though, publication rights are with Alkhaer Publications.

Search Articles

Issue June 2023

Volume 12, June 2023


Table of Contents



World-wide Delivery is FREE

Share this Issue with Friends:


Submit your Paper