The average connectivity matrix of a graph

MaRDI QIDQ6421885zbMATH OpenFDO

Authors Linh Kop Nguyen, Suil O

Publication date 28 December 2022

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: For a graph $G$ and for two distinct vertices $u$ and $v$, let $kappa(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 $$, is an $nimesn$ matrix whose $(u,v)$-entry is $kappa(u,v)/nchoose2$ and let $$ be the spectral radius of $$. 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 $$, which implies a result of Kim and O cite{KO} stating that for any connected graph $G$, we have $$, where $$ and $alph{a}^{\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 $$, and equality in the bound holds only when $G$ is a complete balanced bipartite graph.

This page was built for publication: The average connectivity matrix of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421885)