Fully Indecomposable and Nearly Decomposable Graphs
Mehdi Aaghabali, Saieed Akbari, M. Ariannejad, Z. Tajfirouz · Libraries and Cultural Resources (University of Calgary) · 2014
Let A be an n-square non-negative matrix. If A contains no s\times t zero submatrix, where s + t = n, then it is called fully indecomposable. Also, a graph G is said to be fully indecomposable if its adjacency matrix is fully indecomposable. In this paper we provide some necessary and sucient conditions for a graph to be fully indecomposable. Among other results we prove that a regular connected graph is fully indecomposable if and only if it is not bipartite.