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

NINA PARDAL; GUILLERMO ALFREDO DURÁN; GRIPPO, L.N.; MARTÍN DARÍO SAFE

Workshop; 8th Latin-American Workshop on Cliques in Graphs; 2018

A (0, 1)-matrix has the Consecutive Ones Property (C1P) for therows if there is a permutation of its columns such that the ones ineach row appear consecutively. We say a (0, 1)-matrix is nested ifit has the consecutive ones property for the rows (C1P) and everytwo rows are either disjoint or nested. We say a (0, 1)-matrix is2-nested if it has the C1P and admits a partition of its rows intotwo sets such that the submatrix induced by each of these sets isnested. 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 adjacencybetween vertices in S and K is nested (resp. 2-nested). In this work,we characterize nested and 2-nested matrices by minimal forbiddensubmatrices. This characterization leads to a minimal forbidden induced subgraph characterization of these graph classes, which aresuperclasses of threshold graphs and subclasses of split and circlegraphs.