Graph functions maximized on a path

Abstract

Given a connected graph $G$of order $n$ and a nonnegative symmetric matrix $A=\left[a_{i,j}\right]$ of order $n,$ define the function $F_A\left(G\right)$ as% \[ F_{A}\left( G\right) =\sum_{1\leq i<j\leq n}d_{G}\left( i,j\right) a_{i,j}, \] where $d_G\left(i,j\right)$ denotes the distance between the vertices $i$ and $j$ in $G.$ In this note it is shown that $F_A\left(G\right)\le F_A\left(P\right)$for some path of order $n.$ Moreover, if each row of $A$ has at most one zero off-diagonal entry, then $F_A\left(G\right)<F_A\left(P\right)$for some path of order $n,$ unless $G$ itself is a path. In particular, this result implies two conjectures of Aouchiche and Hansen: - the spectral radius of the distance Laplacian of a connected graph $G$ of order $n$ is maximal if and only if $G$ is a path; - the spectral radius of the distance signless Laplacian of a connected graph $G$ of order $n$ is maximal if and only if $G$ is a path.

11 pages