Inequalities between distance-based graph polynomials

I. Gutman ; Olga Miljković ; B. Zhou ; M. Petrović

Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 31 (2006), p. 57

Résumé

In a recent paper {\rm [ I. Gutman, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) {\bf 131} (2005) 1--7]}, the Hosoya polynomial $H=H(G,\lambda)$ of a graph $G$ , and two related distance--based polynomials $H_1=H_1(G,\lambda)$ and $H_2=H_2(G,\lambda)$ were examined. We now show that $\max\{\delta H_1 - \delta^2 H , \Delta H_1 - \Delta^2 H\} �eq H_2 �eq \Delta H_1 - \delta \Delta H$ holds for all graphs $G$ and for all $\lambda \geq 0$ , where $\delta$ and $\Delta$ are the smallest and greatest vertex degree in $G$ . The answer to the question which of the terms $\delta\,H_1 - \delta^2\,H$ and $\Delta\,H_1 - \Delta^2\,H$ is greater, depends on the graph $G$ and on the value of the variable $\lambda$ . We find a number of particular solutions of this problem.

Détail

Classification : 05C12 05C05
Keywords: Graph polynomial, distance (in graph)