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

PARDAL, NINA; SAFE, MARTIN; GRIPPO, LUCIANO; DURÁN, GUILLERMO

MATEMáTICA CONTEMPORâNEA

Sociedade Brasileira de Matematica

Lugar: Rio de Janeiro; Año: 2019 vol. 46 p. 119 - 128

0103-9059

A (0; 1)-matrix has the Consecutive Ones Property (C1P) for the rowsif there is a permutation of its columns such that the ones in each rowappear consecutively. We say a (0; 1)-matrix is nested if it has the con-secutive ones property for the rows (C1P) and every two rows are eitherdisjoint or nested. We say a (0; 1)-matrix is 2-nested if it has the C1P andadmits a partition of its rows into two sets such that the submatrix inducedby 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 theadjacency between vertices in S and K is nested (resp. 2-nested). In thiswork, we characterize nested and 2-nested matrices by minimal forbiddensubmatrices. This characterization leads to a minimal forbidden inducedsubgraph characterization of these graph classes, which are superclassesof threshold graphs and subclasses of split and circle graphs.