On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs

Abstract

A $(0,1)$-matrix has the Consecutive Ones Property (C1P) for the rows if there is a permutation of its columns such that the ones in each row appear consecutively. We say a $(0,1)$-matrix is nested if it has the consecutive ones property for the rows (C1P) and every two rows are either disjoint or nested. We say a $(0,1)$-matrix is 2-nested if it has the C1P and admits a partition of its rows into two sets such that the submatrix induced by each of these sets is nested. We say a split graph $G$ with split partition $(K,S)$ is nested (resp.\ 2-nested) if the matrix $A(S,K)$ which indicates the adjacency between vertices in $S$ and $K$ is nested (resp.\ 2-nested). In this work, we characterize nested and 2-nested matrices by minimal forbidden submatrices. This characterization leads to a minimal forbidden induced subgraph characterization for these classes of graphs, which are a superclass of threshold graphs and a subclass of split and circle graphs.

arXiv comment6 pages. Presented in the LatinAmerican Workshop on Cliques in Graphs 2018. Sent to publish in the special issue devoted to this conference of Mathematica Contemporânea

Cited by in corpus (1)

• 2-nested matrices: towards understanding the structure of circle graphs