Bulletin, Classe des Sciences Mathématiques et Naturelles, Sciences mathématiques naturelles / sciences mathematiques Vol. CXXXIII, No. 31, pp. 57–68 (2006)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

Pick a mirror

## Inequalities between distance–based graph polynomials

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

Faculty of Science, University of Kragujevac, P. O. Box 60, 34000 Kragujevac, Serbia
Department of Mathematics, South China Normal University, Guangzhou 510631, P. R. China

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)