Groupe d’études et de recherche en analyse des décisions

# Bounds on the Index of the Signless Laplacian of a Graph

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

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)$.

, 14 pages

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