On the Edge-Residual Number and the Line Completion Number of a Graph

Abstract

In this paper we introduce the edge-residual number $\rho (G)$ of a graph $G$. We give tight upper bounds for $\rho (G)$ in terms of the eigenvalues of the Laplacian matrix of the line graph of $G$. In addition, we investigate the relation between this novel parameter and the line completion number for dense graphs. We also compute the line completion number of complete bipartite graphs $K_{m,n}$ when either $m=n$ or both $m$ and $n$ are even numbers. This partially solves an open problem of Bagga, Beinecke and Varma [2].