The average connectivity matrix of a graph

Abstract

For a graph $G$ and for two distinct vertices $u$ and $v$, let $\hat{I}º(u,v)$ be the maximum number of vertex-disjoint paths joining $u$ and $v$ in $G$. The average connectivity matrix of an $n$-vertex connected graph $G$, written $A_{\bar{\hat{I}}º}(G)$, is an $n\times n$ matrix whose $(u,v)$-entry is $\hat{I}º(u,v)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and let $\ddot{I}(A_{\bar{\hat{I}}º}(G))$ be the spectral radius of $A_{\bar{\hat{I}}º}(G)$. In this paper, we investigate some spectral properties of the matrix. In particular, we prove that for any $n$-vertex connected graph $G$, we have $\ddot{I}(A_{\bar{\hat{I}}º}(G))\le \frac{4\hat{I}{\pm }^{\prime }(G)}{n}$, which implies a result of Kim and O \cite{KO} stating that for any connected graph $G$, we have $\bar{\hat{I}}º(G)\le 2\hat{I}{\pm }^{\prime }(G)$, where $\bar{\hat{I}}º(G)={\sum }_{u,v\in V(G)}\frac{\hat{I}º(u,v)}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ and $\hat{I}{\pm }^{\prime }(G)$ is the maximum size of a matching in $G$; equality holds only when $G$ is a complete graph with an odd number of vertices. Also, for bipartite graphs, we improve the bound, namely $\ddot{I}(A_{\bar{\hat{I}}º}(G))\le \frac{(n-\hat{I}{\pm }^{\prime }(G))(4\hat{I}{\pm }^{\prime }(G)-2)}{n(n-1)}$, and equality in the bound holds only when $G$ is a complete balanced bipartite graph.