Inequalities between distance–based graph polynomials

I. Gutman, Olga Miljkovic, B. ZHOU and M. Petrovic

Abstract: In a recent paper [ I. Gutman, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) 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\} \leq H_2 \leq \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.

Keywords: Graph polynomial, distance (in graph)

Classification (MSC2000): 05C12, 05C05

Full text of the article: (for faster download, first choose a mirror)

• Compressed DVI file (16 kilobytes)
• Compressed PostScript file (116 kilobytes)
• PDF file (104 kilobytes)