Bounds on the Index of the Signless Laplacian of a Graph

Oliveira, Carla Silva; Silva de Lima, Leonardo; de Abreu, Nair Maria Maia; Hansen, Pierre

Let $G=(V,E)$ be a simple, undirected graph of order $n$ and size $m$ with vertex set $V$ , edge set $E$ , adjacency matrix $A$ and vertex degrees $\Delta=d_1 \geq d_2 \geq \dots \geq d_n=\delta$ . The average degree of the neighbor of vertex $v_i$ is $m_i=\frac{1}{d_i} \sum\limits^{n}_{j=1} a_{ij} d_j$ . Let $D$ be the diagonal matrix of degrees of $G$ . Then $L(G)=D(G)-A(G)$ is the Laplacian matrix of $G$ and $Q(G)=D(G) + A(G)$ the signless Laplacian matrix of $G$ . Let $\mu_1 (G)$ denote the index of $L(G)$ and $q_1(G)$ the index of $Q(G)$ . We survey upper bounds on $\mu_1(G)$ and $q_1(G)$ given in terms of the $d_i$ and $m_i$ , as well as of the numbers of common neighbors of pairs of vertices. It is well known that $\mu_1(G) \leq q_1(G)$ . We show that many but not all upper bounds on $\mu_1(G)$ are still valid for $q_1(G)$ .

Paru en septembre 2007 , 14 pages

Ce cahier a été révisé en avril 2008