On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs
Nina Pardal Guillermo A. Durán Luciano N. Grippo Martín D. Safe


        




On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs.
    Nina Pardal Guillermo A. Durán Luciano N. Grippo Martín D. Safe Supported by PIO CONICET UNGS-144-20140100011-CO, UNS Grants PGI 24/L103 and PGI 24/L115, ANPCyT PICT-2017-1315, and MATH-AmSud 18-MATH-01. This work was partially financed by ISCI, Chile (CONICYT PIA FB0816; ICM P-05-004-F), ANPCyT PICT grant 2015-2218 (Argentina) and UBACyT grant 20020170100495BA (Argentina). 
2000 AMS Subject Classification: 05C75, 05C50 and 05C38. Keywords: circle graphs, split graphs, 2-coloring, consecutive ones property, characterization
    
=====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




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. 





§ INTRODUCTION
 

Let A=(a_ij) be a n× m (0,1)-matrix.
We denote a_i. and a_.j the ith row and the jth column of matrix A.
Let l_i = min{ j  a_ij = 1 } and r_i = max{ j  a_ij = 1 } for each i∈{1,…,n}. Two rows a_i. and a_k. are disjoint if there is no j such that a_ij = a_kj = 1.
We say that a_i. is contained in a_k. if for each j such that a_ij = 1 also a_kj = 1. We say that a_i. and a_k. are nested if a_i. is contained in a_k. or a_k. is contained in a_i..
Finally, we say that a_i. and a_k. start (resp. end) in the same column if l_i = l_k (resp. r_i = r_k), 
and we say a_i. and a_k. start (end) in different columns otherwise. 
We say a (0,1)-matrix A has the consecutive ones property for the rows (for short, C1P) if there is permutation of the columns of A such that the 1's in each row appear consecutively. 
 Tucker characterized all the minimal forbidden submatrices for the C1P, later known as Tucker matrices. For the complete list of Tucker matrices, see <cit.>, where a graphic representation of them can be found in Figure 3. 
 
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 for the rows and there is a partition S_1, S_2 of the rows such that each submatrix obtained is nested.

All graphs in this work are simple, undirected, with no loops and no multiple edges. The pair (K,S) is a split partition of a graph G if {K,S} is a partition of the vertex set of G and the vertices of K (resp. S) are pairwise adjacent (resp. nonadjacent), and we denote it G=(K,S). A graph G is a split graph if it admits some split partition. Let G be a split graph with split partition (K,S), n=| S|, and m=| K|. Let s_1, …, s_n and v_1, …, v_m be linear orderings of S and K, respectively. Let A= A(S,K) be the n× m matrix defined by A(i,j)=1 if s_i is adjacent to v_j and A(i,j)=0, otherwise.

A split graph G = (K,S) is nested (resp. 2-nested) if there is a linear ordering Π of K, such that the associated matrix A(S,K) is nested (resp. 2-nested) and if its columns are ordered as in Π then the ones in each row occur in consecutive columns.

Circle graphs <cit.> are intersection graphs of chords in
a circle. These graphs were characterized by Bouchet <cit.> in 1994 by forbidden induced subgraphs under local complementation. However, no complete characterizations of circle graphs by forbidden induced subgraphs of the graph itself are known. It follows from the definition that nested and 2-nested graphs are common subclasses of circle graphs. 
Furthermore, nested and 2-nested graphs are also a superclass of threshold graphs (see Golumbic <cit.> for more details on these definitions).

The problem of characterizing 2-nested graphs by minimal forbidden induced subgraphs arises as a natural subproblem in our ongoing efforts to obtain the same kind of characterization of those split graphs that are circle graphs. 
We started by considering a split graph H such that H is minimally non-circle. Since comparability graphs are a subclass of circle graphs, in particular H is not a comparability graph. Notice that permutation graphs are those comparability graphs for which their complement is also a comparability graph. It is easy to prove that permutation graphs are precisely those circle graphs having a circle model with an equator. See Gallai <cit.> for the complete list of minimal forbidden subgraphs of comparability graphs. Using the list of minimal forbidden subgraphs of comparability graphs and the fact that H is also a split graph, we conclude that H contains either a tent, a 4-tent, a co-4-tent or a net as a subgraph. We first considered the case in which H contains an induced tent as a subgraph, thus reaching a problem when trying to give a circle model for H.
Once analyzed the compatibilities between the vertices in the complete and independent partitions of such a graph, it arises that there is exactly one subclass –which we denoted α– of independent vertices for which both endpoints of each vertex could be entirely drawn in two distinct areas of the circle model, when for every other vertex there is a unique possible placement. Hence, for the subgraph induced by taking the tent graph union the subclass α to admit a circle model, the subclass α must be partitioned into two disjoint subsets such that, for each subset, every pair of vertices are either disjoint or nested, thus leading to the definition of 2-nested graphs.






§ NESTED MATRICES


We begin by giving the following characterization of nested matrices. 

	A (0,1)-matrix is nested if and only if it contains no G_0 as a submatrix (see Figure <ref>).









Since no Tucker matrix has the C1P and the rows of G_0 are neither disjoint nor nested, no nested matrix contains a Tucker matrix or G_0 as submatrices. Conversely, as each Tucker matrix contains G_0 as a submatrix, every matrix containing no G_0 as a submatrix is a nested matrix.



	A split graph is nested if and only if it contains no induced gem.






§ 2-NESTED MATRICES




We define the following matrices, since they play an important role in the sequel. 




 





	A (0,1)-matrix A is 2-nested if and only if there is a linear ordering Π of the columns such that the matrix A with its columns ordered according to Π does not contain any Tucker matrix, or F_0, F_1(k), F_2(k) for every odd k ≥ 5 as a configuration.





We define the auxiliary graph H(A)=(V,E) where the vertex set V= { w_1, …, w_n } has one vertex for each row in A, 
and two vertices w_i and w_k in V are adjacent if and only if the rows a_i. and a_k. are neither disjoint nor nested. By abuse of language, w_i will refer to both the vertex w_i in H(A) and the row a_i. of A. In particular, the definitions given in the introduction apply to the vertices in H(A); i.e., we say two vertices w_i and w_k in H(A) are nested (resp. disjoint) if the corresponding rows a_i. and a_k. are nested (resp. disjoint). And two vertices w_i and w_k in H(A) start (resp. end) in the same column if the corresponding rows a_i. and a_k. start (resp. end) in the same column. 
It follows from the definition of 2-nested matrices that A is a 2-nested matrix if and only if there is a bicoloring of the auxiliary graph H(A) or, equivalently, if H(A) is bipartite (i.e., H(A) does not contain cycles of odd length).


 
	
	Since A admits a C1P, then A contains no Tucker matrices. Moreover, if A contains F_0, F_1(k) or F_2(k) for some odd k ≥ 5, since the corresponding subgraphs in H(A) of every such matrix induces an odd cycle, then it follows that H(A) does not admit a proper 2-coloring and this results in a contradiction. Therefore, A does not contain any F_0, F_1(k) or F_2(k) for any odd k≥ 5 as a configuration.	
	
	

	
	Conversely, let Π be a linear ordering of the columns such that the matrix A does not contain any F_0, F_1(k), F_2(k) for any odd k≥ 5 or Tucker matrices as configurations.
	Due to Tucker's Theorem, since there are no Tucker submatrices in A,
	the matrix A has the C1P. 
	
	Towards a contradiction, suppose that the auxiliary graph H(A) is not bipartite. Hence there is an induced odd cycle C in H(A).

	Suppose first that H(A) has an induced odd cycle C = w_1, w_2, w_3, w_1 of length 3, and suppose without loss of generality that the first rows of A are those corresponding to the cycle C. 
	Since w_1 and w_2 are adjacent, both begin and end in different columns. The same holds for w_2 and w_3, and w_1 and w_3. We assume without loss of generality that the vertices start in the order of the cycle, in other words, that l_1 < l_2 < l_3. 
	
	Since w_1 starts first, it is clear that a_2 l_1 = a_3 l_1 = 0, thus the column a_. l_1 of A is the same as the first column of the matrix F_0.

	Since A has the C1P and w_1 and w_2 are adjacent, then a_1 l_2 = 1. 
	As stated before, w_2 starts before w_3 and thus a_3 l_2 = 0. Hence, column a_. l_2 is equal to the second column of F_0.
	
	The third column of F_0 is a_. l_3, for w_3 is adjacent to w_1 and w_2, hence it is straightforward that a_1 l_3 = a_2 l_3 = a_3 l_3 = 1.
	
	To find the next column of F_0, let us look at column a_. (r_1+1). Notice that r_1 + 1 > l_3. Since w_1 is adjacent to w_2 and w_3, and w_2 and w_3 both start after w_1, then necessarily a_2 (r_1+1) = a_3 (r_1+1) = 1, and thus a_. (r_1+1) is equal to the fourth column of F_0.
	
	Finally, we look at the column a_. (r_2 +1). Notice that r_2 +1 > r_1 + 1. 
	Since A has the C1P, a_1 (r_2 +1) = 0 and r_2 +1 > r_1+1, then a_1 (r_2+1) =0 and a_3 (r_2+1) = 1, which is equal to last column of F_0. Therefore we reached a contradiction that came from assuming that there is a cycle of length 3 in H(A).
	
	Suppose now that H(A) has an induced odd cycle C = w_1, …, w_k, w_1 of length k ≥ 5. We assume without loss of generality that the first k rows of A are those in C and that A is ordered according to the C1P.
	
	 
		Let w_i, w_j be vertices in H(A). If w_i and w_j are adjacent and w_i starts before w_j, then a_i r_i = a_j r_i = 1 and a_i (r_i+1) = 0, a_j (r_i +1) = 1.
	

 
	If l_i-1 > l_i and l_i+1 > l_i for some i = 3, …, k-1, then for all j≥ i+1, w_j is nested in w_i-1. The same holds if l_i-1 < l_i and l_i+1 < l_i.
	Since l_i-1 > l_i and l_i+1 > l_i, then w_i-1 and w_i+1 are not disjoint, thus necessarily w_i+1 is nested in w_i-1. It follows from this argument that this holds for j ≥ i+1.


Notice that w_2 and w_k are nonadjacent, hence they are either disjoint or nested. Using this fact and Remark <ref>, we split the proof into two cases.


	w_2 and w_k are nested 
	


We may assume without loss of generality that w_k is nested in w_2, for if not, we can rearrange the cycle backwards as w_1, w_k, w_k-1, …, w_2, w_1. Moreover, we will assume without loss of generality that both w_2 and w_k start before w_1. First, we need the following Claim.

 
	If w_2 and w_k are nested, then w_i is nested in w_2, for i = 4, …, k-1.


Suppose first that w_1 and w_3 are disjoint, and towards a contradiction suppose that w_2 and w_4 are disjoint. In this case, l_4 < l_3 < r_4 < l_2 < r_3 < r_2. 
The contradiction is clear if k=5.
If instead k>5 and w_5 starts before w_4, then r_i < l_3 for all i > 5, which contradicts the assumption that w_k is nested in w_2. Hence, necessarily w_5 is nested in w_3 and w_5 and w_2 are disjoint. This implies that l_3 < l_5 < r_4 < r_5 < l_2 and once more, r_i < l_2 for all i >5, which contradicts the fact that w_k is nested in w_2.


Suppose now that w_3 is nested in w_1. Towards a contradiction, suppose that w_4 is not nested in w_2. Thus, w_2 and w_4 are disjoint since they are nonadjacent vertices in H(A).
Notice that, if w_3 is nested in w_1, then l_2 < l_3 and r_2 < r_3.
Furthermore, since w_4 is adjacent to w_3 and nonadjacent to w_2, then l_3 < r_2 < l_4 < r_3 < r_4. This holds for every odd k≥ 5.

If k=5, since w_5 is nested in w_2, then r_5 < r_2 < l_4, which results in a contradiction for w_4 and w_5 are adjacent.

Suppose that k>5. If w_2 and w_i are disjoint for all i= 5, …, k-1, then w_k-1 and w_k are nonadjacent for w_k is nested in w_2, which results in a contradiction. Conversely, if w_i and w_2 are not disjoint for some i > 3, then they are adjacent, which also results in a contradiction that came from assuming that w_2 and w_4 are disjoint. Therefore, since w_4 is nested in w_2, w_2 and w_i are nonadjacent and w_i is adjacent to w_i+1 for all i >4, then necessarily w_i is nested in w_2, which finishes the proof of the Claim. 

 
	Suppose that w_2 and w_k are nested. Then, if w_3 is nested in w_1, then l_i > l_i+1 for all i=3, …, k-1. If instead w_1 and w_3 are disjoint, then l_i < l_i+1 for all i=3, …, k-1.








Recall that, by the previous Claim, since w_i is nested in w_2 for all i = 4, …, k, in particular w_4 is nested in w_2. Moreover, since w_3 and w_4 are adjacent, notice that, if w_3 is nested in w_1, then l_3 > l_4, and if w_1 and w_3 are disjoint, then l_3 < l_4.

It follows from Remark <ref> that, if l_5 > l_4, then w_i is nested in w_3 for all i = 5, …, k, which contradicts the fact that w_1 and w_k-1 are adjacent. The proof of the first statement follows from applying this argument successively.

The second statement is proven analogously by applying Remark <ref> if l_5 < l_4, and afterwards successively for all i > 4. 

If w_1 and w_3 are disjoint, then we obtain F_2(k) first, by putting the first row as the last row, and considering the submatrix given by columns j_1 = l_1 -1, j_2 = l_3, …, j_i = l_i+1, …, j_k = r_1+1 (using the new ordering of the rows).
If instead w_3 is nested in w_1, then we obtain F_1(k) by taking the submatrix given by the columns j_1 = l_1 -1, j_2 = r_k, …, j_i = l_k -i +2, …, j_k-1 = r_3.


	w_2 and w_k are disjoint 
	


We assume without loss of generality that l_2 < l_1 and l_k > l_1.

 
	If w_2 and w_k are disjoint, then l_i < l_i+1 for all i=2, …, k-1.


Notice first that, in this case, w_i is nested in w_1, for all i= 3, …, k-1. If not, then using Remark <ref>, we notice that it is not possible for the vertices w_1, …, w_k to induce a cycle. This implies, in particular, that w_3 is nested in w_1 and thus l_2 < l_3.
Furthermore, using this and the same remark, we conclude that l_i < l_i+1 for all i = 2, …, k-1, therefore proving Claim <ref>. 
 
In this case, we obtain F_2(k) by considering the submatrix given by the columns j_1 = l_1 -1, j_2 = l_3, …, j_i = l_i+1, …, j_k = r_1+1.




10

B94 A. Bouchet, Circle graph obstructions, J. Combin. Theory B 60 (1994), 107–144.


EI71 S. Even, A. Itai, Queues, stacks and graphs, in: A. Kohavi, A. Paz (Eds.), Theory of Machines and Computations, Academic Press, New York (1971), 71–86.


G67 T. Gallai, Transitiv orientierbare Graphen, Acta Mathematica Academiae Scientiarum Hungaricae 18 (1-2) (1967), 25–66.


G04 M. C. Golumbic, Algorithmic graph theory and perfect graphs, Elsevier Science B.V., Amsterdam (2004). 


T72 A.C. Tucker, A structure theorem for the consecutive 1's property, J. Combin. Theory 12 (B) (1972), 153–162.

  





=0pt
Nina Pardal
Instituto de Cálculo
Universidad de Buenos Aires
Buenos Aires, Argentina
npardal@ic.fcen.uba.ar

   
=0pt
Guillermo A. Durán
Instituto de Cálculo
Universidad de Buenos Aires
Buenos Aires, Argentina
gduran@ic.fcen.uba.ar



=0pt
Luciano N. Grippo 
Instituto de Ciencias
UNGS
Buenos Aires, Argentina
lgrippo@ungs.edu.ar


   
=0pt
Martín D. Safe
INMABB,  Depto. de Matemática
Univ. Nacional del Sur–CONICET
Bahía Blanca, Argentina
msafe@uns.edu.ar



