On some subclasses of interval catch digraphs

Sanchita Paul^∗ , Shamik Ghosh

Department of Mathematics, Jadavpur University, Kolkata - 700 032, India.

sanchitajumath@gmail.com, ghoshshamik@yahoo.com

^∗Corresponding author

A digraph G = (V, E) is an interval catch digraph if for each vertex v ∈ V , one can associate an interval on real line and a point within it (say (Iv, pv)) in such a way that uv ∈ E if and only if p^v ∈ Iu. It was introduced by Maehara in 1984. It has many applications in real world situations like networking and telecommunication. In his introducing paper Maehara proposed a conjecture for the characterization of central interval catch digraph (where p^v is the mid-point I^v for each v ∈ V ) in terms of forbidden subdigraphs. In this paper, we disprove the conjecture by showing counter examples. Also we characterize this digraph by defining a suitable mapping from the vertex set to the real line. We study oriented interval catch digraphs and characterize an interval catch digraph when it is a tournament. Finally, we characterize a proper interval catch digraph and establish relationships between these digraph classes.

Keywords: interval catch digraph, interval graph, proper interval graph, oriented graph, tournament Mathematical Subject Classification: 05C20, 05C62, 05C75

DOI: 10.5614/ejgta.2022.10.1.10

1. Introduction

Intersection graphs have many important applications in problems related to real-world situations. Because of its diverse applications in network science, different kinds of intersection graphs were introduced in modeling various geometric objects. Among them, interval graph is the most important one. A simple graph G = (V, E) is an interval graph if one can map each vertex into

Received: 25 September 2019, Revised: 18 January 2022, Accepted: 13 February 2022.

an interval on the real line so that any two vertices are adjacent if and only if their corresponding intervals intersect. In 1984 Maehara [11] introduced an analogous concept for directed graphs (in short, digraphs). He defined a catch digraph of F as a digraph G = (V, E) in which uv ∈ E if and only if u 6= v and p^v ∈ S^u where F = {(Su, pu) | u ∈ V } is a family of pointed sets (a set with a point within it) in a Euclidean space. The digraph G is said to be represented by F. Later on, interval catch digraphs (in brief, ICD) was also studied by Prisner [14] in 1989 where S^u is represented by an interval I^u in the real line. A digraph G = (V, E) is unilaterally connected if for each pair of distinct vertices u, v ∈ V , there is a directed path from u to v or from v to u (or both). The underlying graph of a digraph G = (V, E) is an undirected graph U(G) = (V 0 , E⁰ ) where V ⁰ = V and E ⁰ = {uv | uv ∈ E or vu ∈ E}. An oriented graph G = (V, E) is a digraph with no (directed) cycle of length two, i.e., if uv ∈ E, u, v ∈ V , then vu /∈ E. A tournament is an oriented graph G = (V, E) where every pair of distinct vertices are adjacent, i.e., for any distinct pair u, v ∈ V , either uv ∈ E or vu ∈ E (but not both).

In our paper, we study some natural subclasses of ICD, namely central interval catch digraph (in brief, central ICD), oriented interval catch digraph (in brief, oriented ICD) and proper interval catch digraph (in brief, proper ICD). A central ICD is an ICD where the points p^u are the center points of the intervals Iu. This digraph was introduced by Maehara [11] in name of "interval digraph"¹ and he proposed a conjecture for characterization of central ICD in terms of forbidden subdigraphs. We disprove the conjecture by showing counter examples. Also we characterize this digraph by defining a suitable mapping from the vertex set to the real line. We prove that an oriented ICD is acyclic and study various properties of it. Then we characterize adjacency matrix of an oriented ICD when it is a tournament. A proper ICD is an ICD where no interval contains other properly. We obtain characterization of the adjacency matrix of a proper ICD. In conclusion we discuss relationships between these classes of digraphs. Henceforth undirected graphs will be called simply graphs. For some recent applications of ICD and in general, catch digraphs one may consult [4, 5, 6, 13].

2. Preliminaries

A proper interval graph G is an interval graph in which there is an interval representation of G such that no interval is a proper subinterval of other. A unit interval graph is an interval graph in which there is an interval representation of G such that all intervals have the same length. Let v ∈ V for any graph G = (V, E). Then the set N[v] = {u ∈ V | u is adjacent to v} ∪ {v} is the closed neighborhood of v in G. The reduced graph G˜ is obtained from G by merging vertices having same closed neighborhood. G(n, r) is a graph with n vertices x1, x2, . . . , xⁿ such that xⁱ is adjacent to x^j if and only if 0 < |i − j| ≤ r, where r < n is a positive integer [12]. Among many characterizations [8, 9] of proper interval graph we list the following which will serve our purpose.

Theorem 2.1. [10] Let G = (V,E) be an interval graph. Then the following are equivalent:

1. G is a proper interval graph.

¹The term "interval digraph" is now commonly used to mean a different digraph. The comparison between ICD and interval digraphs are described in details in [15]. We are not repeating this here.

• 2. G is a unit interval graph.
• 3. G˜ is an induced subgraph of G(n, r) for some positive integers n, r with n > r.
• 4. There is an ordering of V such that for all v ∈ V , elements of N[v] are consecutive (the closed neighborhood condition).
• 5. There exists an ordering '<' on V such that u < v < w and uw ∈ E imply uv and vw ∈ E. (umbrella property)

The following characterization is known for interval catch digraphs.

Theorem 2.2. [14] Let G = (V, E) be a simple digraph. Then G is an ICD if and only if there exists an ordering " < " of V such that

\[for \ x < y < z \in V, \ xz \in E \Longrightarrow xy \in E \ \ and \ \ zx \in E \Longrightarrow zy \in E. \tag{2.1}\]

A (0, 1)-matrix is said to satisfy consecutive 1's property for rows if its columns can be permuted in such a way that the 1's in each row occur consecutively. The augmented adjacency matrix A∗ (G) of a digraph G is obtained from the adjacency matrix A(G) of G by replacing 0's by 1's along the principal diagonal. It follows from (2.1) that with respect to the ordering of vertices of G = (V, E) described in Theorem 2.2, A^∗ (G) satisfy consecutive 1's property for rows. We call this ordering an ICD ordering of V . This ordering is not unique for an ICD. For a simple digraph G = (V, E), we denote the set of (closed) neighbors {v ∈ V | uv ∈ E} ∪ {u} of u by d ⁺[u] for each u ∈ V . It is clear that elements of d ⁺[u] are consecutive in an ICD ordering for each u ∈ V if G is an ICD. Moreover, if {(Iu, pu) | u ∈ V } is a pointed interval representation of an ICD G, then the points can be made distinct by slight adjustment and the increasing ordering of these points is an ICD ordering of the corresponding vertices. In the following we frequently use the above conditions equivalent to (2.1) without explicitly mentioning this every time.

3. Central interval catch digraphs

In 1984, Maehara posed the following conjecture:

Maehara's conjecture [11]: If a digraph G has no induced subdigraph isomorphic to one of the digraphs in Figure 1 and A^∗ (G) satisfy the consecutive 1's property for rows, then G is a central ICD.

Figure 1: Maehara's forbidden digraphs for central ICD

We show the digraphs G1, G2, G³ in Example 3.2 disprove the conjecture. To see this we obtain the following necessary condition of a central ICD.

Proposition 3.1. Let G = (V, E) be a central ICD. Then there is an ordering of vertices \(V = \{v_1, v_2, \dots, v_n\}\) which satisfies (2.1) and the following condition:

for any \[i < j\], either \(i_1 \leqslant j_1\) or \(i_2 \leqslant j_2\), (3.1)

where \(i_1\) and \(i_2\) be the least and the highest numbers such that \(i_1 = i\) or \(v_i v_{i_1} \in E\) and \(i_2 = i\) or \(v_i v_{i_2} \in E\) for each i = 1, 2, ..., n.

Proof. Let G=(V,E) be represented by \(\{(I_i,c_i)|i\in V\}\) where \(I_i=[a_i,b_i]\) is an interval and \(c_i\) be its center point. We arrange vertices of G according to the increasing order of their center points. It is easy to check G satisfy (2.1) with respect to this ordering. On contrary, let us assume for some \(i< j,\ i_1>j_1\) and \(i_2>j_2\). Then \(j_1< i_1\leqslant i< j\leqslant j_2< i_2\). Now \(v_jv_{j_1}\in E,v_iv_{j_1}\notin E\) imply \(c_{j_1}\in I_j\) and \(c_{j_1}\notin I_i\). Since \(c_{j_1}\notin [a_i,b_i]\), either \(c_{j_1}< a_i\) or \(c_{j_1}>b_i\). If \(c_{j_1}>b_i\), then \(c_{i_1}\geq c_{j_1}>b_i\) as \(i_1>j_1\). But then \(v_iv_{i_1}\notin E\) which is a contradiction. Thus \(a_j\leq c_{j_1}< a_i\leq c_i\leq c_j\). Hence \([a_i,c_i]\subset [a_j,c_j]\). Now as \(v_iv_{i_2}\in E,\ c_{i_2}\in I_i\subset I_j\) which implies \(v_jv_{i_2}\in E\). But then \(i_2\leq j_2\) which is again a contradiction. Hence the proof follows.

\[G_1 (a = b = 0, c = 1) G_2 (a = 0, b = c = 1) G_3 (a = b = c = 1) G_4 (a = b = c = 0)\]

Figure 2: Forbidden digraphs for central ICD when |V| = 4 and their augmented adjacency matrices.

Example 3.2. Consider the digraphs \(G_k = (V_k, E_k)\) with vertex set \(V_k\) and edge set \(E_k\) for k = 1, 2, 3, 4 in Figure 2. Note that \(G_4\) is the digraph (a) in Figure 1. From Theorem 2.1 one can easily verify that \(v_1 < v_2 < v_3 < v_4\) and its reverse ordering are the only possible ICD ordering of \(V_k\) for each graph \(G_k\) (i.e., for which \(A^*(G_k)\) satisfies the consecutive 1's property for rows). Now this augmented adjacency matrix (in Figure 2) shows a contradiction to (3.1) for i = 2, j = 3 for each k. Thus these graphs are not central ICD.

In the following we characterize central ICD. Let \(\mathbb{R}^+\) be the set of all positive real numbers.

Theorem 3.3. Let G = (V, E) be a simple digraph. Then G is a central ICD if and only if there exists an injective labeling \(f : V \longrightarrow \mathbb{R}^+\) of vertices \(^2\) which satisfies the following condition:

\[d(i,j) < d(i,k)\] for all \(i,j,k \in \{1,2,\ldots,n\}\) such that \(v_iv_j \in E\) and \(v_iv_k \notin E\) (3.2)

^&lt;sup>2</sup>Given a positive real number labeling, one can easily obtain a positive rational number labeling with slight adjustment and again those can be changed to positive integers by scaling as required. Thus we note that natural number labeling will produce the same class of digraphs.

where d(i, j) = |f(vi) − f(v^j )| for all i, j ∈ {1, 2, . . . , n}. (i.e., every out-neighbor distance is less than every non-out-neighbor distance from a vertex)

Proof. Suppose G = (V, E) be a central ICD with V = {v1, v2, . . . , vn} and {(Iⁱ , ci) | i = 1, 2, . . . , n} be a central point-interval representation of G where vⁱ corresponds to (Ii , ci), i.e., viv^j ∈ E if and only if c^j ∈ Iⁱ and assume that vi's are ordered according to increasing sequence of ci's (without loss of generality, we also assume that ci's are distinct). Define a labeling f : V −→ R ⁺ by f(vi) = cⁱ . This vertices are ordered according to increasing order of their labels. Now let i, j, k ∈ {1, 2, . . . , n} such that viv^j ∈ E and viv^k 6∈ E. We consider following cases:

Case 1. i < j < k or, k < j < i. Then d(i, k) = d(i, j) + d(j, k) > d(i, j) for d(j, k) > 0 as ci's are distinct.

Case 2. i < k < j or, j < k < i. These cases are not possible by (2.1) as G is an ICD.

Case 3. j < i < k or, k < i < j. Now viv^j ∈ E and viv^k 6∈ E imply c^j ∈ Iⁱ but c^k 6∈ Iⁱ . Let r = |Ii| 2 . Since cⁱ is the central point of Iⁱ , we have Iⁱ = [cⁱ − r, cⁱ + r]. Then d(i, j) = |cⁱ − c^j | < r < |cⁱ − ck| = d(i, k).

Conversely, suppose G satisfies (3.2) with a labeling f. Let us arrange vertices according to increasing order of their labels. For each i = 1, 2, . . . , n, define cⁱ = f(vi). Let i¹ and i² be the least and the highest numbers such that i¹ = i or vivⁱ¹ ∈ E and i² = i or vivⁱ² ∈ E. Note that i¹ 6 i 6 i2. Define rⁱ = max {d(i, i1), d(i, i2)} and Iⁱ = [cⁱ − rⁱ , cⁱ + rⁱ ]. We show that {(Iⁱ , ci) | i = 1, 2, . . . , n} is a central point-interval representation of G, i.e., G is a central ICD. As cⁱ is the center point of Iⁱ for each i ∈ {1, . . . , n}, it is sufficient to prove that G is an ICD.

We verify (2.1) to show that G is an ICD. Let i < j < k and viv^k ∈ E. Now d(i, k) = d(i, j) + d(j, k) > d(i, j). So viv^j ∈ E. Let vkvⁱ ∈ E. Again d(k, i) = d(k, j) + d(j, i) > d(k, j). So vkv^j ∈ E as required.

Example 3.4. Consider the digraph D¹ in Figure 5. It can be easily checked that v¹ < v² < v³ < v⁴ is an ICD ordering of D¹ and D¹ is a central ICD with the labeling: f(v1) = 1, f(v2) = 3, f(v3) = 4 and f(v4) = 6.

Interestingly a family of (undirected) graphs satisfying the condition analogous to (3.2) becomes a well known class of graphs, namely, proper interval graphs.

Theorem 3.5. Let G = (V, E) is a graph. Then G is a proper interval graph if and only if there exist an ordering of vertices and an injective labeling f : V → R ⁺ of vertices such that

\[d(u,v) < d(u,w) \text{ for all } u,v,w \in V \text{ such that } uv \in E \text{ but } uw \notin E,\] (3.3)

where d(u, v) = |f(u) − f(v)| for all u, v ∈ V .

Proof. Let G=(V,E) be a proper interval graph. By Theorem 2.1, the reduced graph \(\tilde{G}=(\tilde{V},\tilde{E})\) of G is an induced subgraph of \(G(n,r)=(V_n,E')\) for some \(n,r\in N\) with n>r (see [12]). Let \(V_n=\{x_1,x_2,\ldots,x_n\}\) such that \(x_i\leftrightarrow x_j\) in G(n,r) if and only if \(0<|i-j|\le r\). Let \(\tilde{V}=\{x_{i_1},x_{i_2},\ldots,x_{i_m}\}\) such that \(i_1< i_2<\ldots< i_m\). For convenience, we write \(y_j=x_{i_j}\) for \(j=1,2,\ldots,m\). Define \(f:V\to\mathbb{R}^+\) by \(f(u)=i_j+\frac{k}{z+1}\) if u is a \(k^{\text{th}}\) copy among z copies of \(y_j\) (for any but a fixed permutation of them). We arrange the vertices of V according to the increasing order of vertices in \(\tilde{V}\) keeping copies of same vertices together. Let \(u,v,w\in V\) such that \(u\leftrightarrow v\) and \(u\leftrightarrow w\). Let \(f(u)=i_p,f(v)=i_q\) and \(f(w)=i_t\) for some \(p,q,t\in\{1,2,\ldots,n\}\). Then \(|i_p-i_q|\le r\) and \(|i_p-i_r|>r\). So d(u,v)=|f(u)-f(v)|<|f(u)-f(w)|=d(u,w). Therefore d(u,v)< d(u,w) for all \(u,v,w\in V\) such that \(u\leftrightarrow v\) and \(u\leftrightarrow w\).

Conversely, let G = (V, E) satisfies (3.3) with a labeling f. We arrange the vertices of G according to the increasing order of their labels. Let i < j < k, where \(i, j, k \in \{1, 2, \dots, n\}\) and \(v_i \leftrightarrow v_k\). Then \(d(v_i, v_j) = d(v_i, v_k) - d(v_j, v_k) < d(v_i, v_k)\). Also \(d(v_j, v_k) = d(v_i, v_k) - d(v_i, v_j) < d(v_i, v_k)\). Then by (3.3), \(v_i \leftrightarrow v_j\) and \(v_j \leftrightarrow v_k\). Thus G satisfies umbrella property and hence by Theorem 2.1, G becomes a proper interval graph.

4. Oriented interval catch digraph

We first note that the characterization of an oriented ICD is obvious. A simple digraph G = (V, E) is an oriented ICD if and only if G is oriented and there exists an ordering of vertices in V satisfying (2.1) or, equivalently, there exists an ordering of vertices in V such that \(A^*(G) = (a_{i,j})\) satisfies consecutive 1's property for rows and for each pair \(i \neq j\), \(a_{i,j} = 1\) implies \(a_{j,i} = 0\). Now we study some important properties of oriented ICD.

Theorem 4.1. An oriented ICD is a directed acyclic graph (DAG).

Proof. Let G be an oriented ICD. We first show that G has no induced directed cycles. Note that any induced subdigraph of an ICD is also an ICD by definition. Now it is easy to check that no induced directed cycles of length \(\geq 3\) satisfies (2.1) and so they are not ICD. Finally, since the digraph is oriented, there are no 2-cycles.

Now we use induction on the length of the cycle. Since G has no induced directed cycles, in particular, G has no directed cycles of length 3. Suppose there are no directed cycles of length less than k and G has a directed cycle C of length k > 3. Since C is not induced, there must be a chord. Interestingly, every such arc (chord) forms a smaller directed cycle on one side of it along with some arcs of C. This contradicts the induction hypothesis. \(\Box\)

The following corollary is immediate from the above theorem.

Corollary 4.2. Let G = (V, E) be an oriented ICD. Then every induced 3-cycle of U(G) is transitively oriented in G.

In [11] Maehara proved that an acyclic ICD is a central ICD. Thus we have the following:

Corollary 4.3. Every oriented ICD is a central ICD.

Definition 4.4. Let G be an oriented graph and C be an even chordless cycle of G which is not a directed cycle. Then C is said to be alternatively oriented if any two arcs of C with common end point have opposite directions.

Proposition 4.5. Let G = (V, E) be an oriented ICD and C be a chordless 4-cycle of G. Then C is alternatively oriented.

Proof. Let C = (v1, v2, v3, v4, v1) be a chordless 4-cycle in G. By Theorem 4.1, C is not a directed 4-cycle. Then there are only 3 other (non-isomorphic) options which are described in Figure 3. The first option T¹ is alternatively oriented. The two other options are not ICD. For example, in the case of T2, in order to find an ICD ordering we need the elements of each of the sets {v1, v2, v4}, {v2, v3} and {v3, v4} to be consecutive. Since the ordering is linear and we require elements of sets {v2, v3} and {v3, v4} to be consecutive in that ordering. So we have either v2, v3, v⁴ or v4, v3, v² consecutive in that ordering. But then {v1, v2, v4} cannot be consecutive. So T² is not ICD. Similarly, it can be shown that T³ is not an ICD.

Figure 3: Orientation of 4-cycles which are not directed 4-cycles.

Now being an acyclic oriented graph, an oriented ICD has some rich properties. For example, a unilaterally connected oriented ICD has unique source (vertex of indegree zero) and unique sink (vertex of outdegree zero). Hence it possesses unique hamiltonian path (see [1]). In the following we characterize oriented ICDs which are tournaments.

A Ferrers digraph is a directed graph G = (V, E) whose successor sets are linearly ordered by inclusion, where the successor set of u ∈ V is its set of out-neighbors {v ∈ V | uv ∈ E}. A (0, 1) matrix M is a Ferrers matrix if 1's are clustered in a corner of M. A digraph G is Ferrers digraph if and only if there exists a permutation of vertices of G such that its adjacency matrix is a Ferrers matrix [2, 7]. For a (0, 1)-matrix M, M denotes the matrix obtained from M by interchanging 0's and 1's.

Theorem 4.6. Let G = (V, E) be an oriented ICD. Then G is a tournament if and only if there is an ordering of vertices of G with respect to which the augmented adjacency matrix A^∗ (G) takes one of the following forms:

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

\[or \quad A^*(G) = \begin{array}{c|cccc} v_1 & . & . & v_n \\ v_1 & 1 & 0 & 0 & 0 \\ . & 1 & 1 & 0 & 0 \\ . & 1 & 1 & 1 & 0 \\ v_n & 1 & 1 & 1 & 1 \end{array} = P\]

where M is an upper triangular matrix with all entries on and above the principal diagonal are 1 and other enties are 0; N and P are lower triangular matrices with all entries on and below the principal diagonal are 1 and other entries are 0 and F is a Ferrers matrix.

Proof. Let G = (V, E) be an oriented ICD which is a tournament. We order the vertices of V according to the increasing value of the associated points in their corresponding intervals. Let \(\{v_1, \ldots, v_n\}\) be the required ordering which is in fact, an ICD ordering, i.e., \(\{v_1, \ldots, v_n\}\) satisfies (2.1). Hence \(A = A^*(G)\) satisfies consecutive 1's property for rows with respect to this ordering. For each \(1 \le i \le n\), let \((v_i)_1\) and \((v_i)_2\) be the column numbers where first and last 1 occur in the i-th row. We denote the (i, j)-th entry of the matrix A by \(a_{i,j}\).

Case 1. \[(v_1)_2 = k > 1\].

In this case, \(a_{1,2} = 1\) (as k > 1). So \(a_{2,1} = 0\) as G is a tournament. Hence \((v_1)_1 = 1 < 2 = (v_2)_1\). Now the following subcases may happen.

Subcase 1(a). If \((v_2)_2 = 2\) then \(2 = (v_2)_2 = (v_2)_1\) which implies the vertex \(v_2\) has out degree 0. In this case we define l = 2 (note that the matrix M in the statement is of the order \(l \times l\)).

Subcase 1(b). If \((v_2)_2 > 2\), then we can show that \((v_2)_2 \le (v_1)_2\). If not, let \((v_2)_2 > (v_1)_2\). Then \(a_{1,(v_2)_2} = 0\) which implies \(a_{(v_2)_2,1} = 1\) as G is a tournament. Now \(a_{2,(v_2)_2} = 1\) by definition. Then \(a_{(v_2)_2,2} = 0\). But we have \(a_{(v_2)_2,1} = 1\) and \(a_{(v_2)_2,(v_2)_2} = 1\). This contradicts the consecutive 1's property for the \((v_2)_2\)-th row as \(1 < 2 < (v_2)_2\). Hence \((v_2)_2 \le (v_1)_2\).

Now since \((v_2)_2 > 2\), \(a_{2,3} = 1\) and hence \(a_{3,2} = 0\). Thus \((v_3)_1 = 3\). Let

\[S = \{i \mid (v_i)_1 = i, \ (v_i)_2 \le (v_{i-1})_2, \ 2 \le i \le n\}.\]

Already we have shown that \(2 \in S\). This implies \(S \neq \emptyset\). As |V| is finite S must have a maximum, say, l. First we will show that \(\{i \mid 2 \le i \le l\} \subseteq S\). As \(2 \in S\), applying induction we assume \(\{2, 3, \ldots, j\} \subseteq S\). If \(j + 1 \le l\), then we show that \(j + 1 \in S\).

If \((v_j)_2 = j\) then \(a_{j,l} = 0\) as l > j. Thus \(a_{l,j} = 1\) and so \((v_l)_1 \le j < l\) which contradicts \(l \in S\). Therefore \((v_j)_2 > j\). But then \(a_{j,j+1} = 1\) which implies \(a_{j+1,j} = 0\) and so \((v_{j+1})_1 = j+1\). Next we show \((v_{j+1})_2 \le (v_j)_2\).

On contrary let \((v_{j+1})_2 > (v_j)_2\). Since \((v_j)_2 > j\), we have \((v_{j+1})_2 \ge j+1\). Now if \((v_{j+1})_2 = j+1\), then \((v_{j+1})_2 \le (v_j)_2\) as \((v_j)_2 > j\). So suppose \((v_{j+1})_2 > j+1\). Now \(a_{j,(v_{j+1})_2} = 0\) as we have assumed \((v_{j+1})_2 > (v_j)_2\). Thus \(a_{(v_{j+1})_2,j} = 1\). Again \(a_{j+1,(v_{j+1})_2} = 1\) implies \(a_{(v_{j+1})_2,j+1} = 0\). But \(a_{(v_{j+1})_2,(v_{j+1})_2} = 1\). This contradicts the consecutive 1's property for \((v_{j+1})_2\)-th row as \(j < j+1 < (v_{j+1})_2\). So we must have \((v_{j+1})_2 \le (v_j)_2\) and hence \(j+1 \in S\). This completes the induction. Therefore \(\{i \mid 2 \le i \le l\} \subseteq S\) and so

\[(v_i)_1 = i, (v_i)_2 \le (v_{i-1})_2\] for all \(i\) with \(2 \le i \le l\).

Now we will show \(l \le k = (v_1)_2\) and \((v_l)_2 = l\). On contrary let l > k. Then \(a_{1,l} = 0\) as \(k = (v_1)_2\). This imply \(a_{l,1} = 1\). Then \((v_l)_1 = 1 < l\) which contradicts \(l \in S\). Therefore \(l \le k\).

Now if \((v_l)_2 > l\) then \(a_{l,l+1} = 1\) which imply \(a_{l+1,l} = 0\), i.e., \((v_{l+1})_1 = v_{l+1}\). But \(l+1 \notin S\). This implies \((v_{l+1})_2 > (v_l)_2 > l\). Hence \(a_{l,(v_{l+1})_2} = 0\) which imply \(a_{(v_{l+1})_2,l} = 1\). But \(a_{(v_{l+1})_2,l+1} = 0\) as \(a_{l+1,(v_{l+1})_2} = 1\) and \(a_{(v_{l+1})_2,(v_{l+1})_2} = 1\). Thus \((v_{l+1})_2 \neq l+1\) and so \((v_{l+1})_2 > l+1\). Then we have a contradiction in the consecutive 1's property for the \((v_{l+1})_2\)-th row as \(l < l+1 < (v_{l+1})_2\). So \((v_l)_2 = l\). Already we have \((v_l)_1 = l\). Thus the l-th row contains only one 1 at the position (l,l).

Therefore the rows \(\{1,2,\ldots,l\}\) form upper triangular matrix M with all entries on and above diagonal as 1 and F becomes a Ferrers matrix formed by the rows \(\{1,2,\ldots,l\}\) and columns \(\{l+1,l+2,\ldots,n\}\) as \((v_l)_2=l\leq (v_{l-1})_2\leq \ldots \leq (v_1)_2=k\). As G forms a tournament, matrix formed by rows \(\{l+1,l+2,\ldots,n\}\) and columns \(\{1,2,\ldots,l\}\) is \(\overline{F^T}\).

Now the only remaining thing is to show \((v_i)_2 = i\) for all i > l. On contrary, let there exist some i where \(l < i \le n\) for which \((v_i)_2 > i\). From this it follows \(a_{i,i+1} = 1\) which implies \(a_{i+1,i} = 0\) i.e., \((v_{i+1})_1 = i+1\). Now since \((v_l)_2 = l\), \(a_{l,i+1} = 0\) and so \(a_{i+1,l} = 1\) which is a contradiction as \((v_{i+1})_1 = i+1 > l\). So we have \((v_i)_2 = i\) for all i > l. Thus we get the required lower triangular matrix N formed by the vertices \(\{v_{l+1}, v_{l+2}, \ldots, v_n\}\).

Case 2. \[(v_1)_2 = v_1\].

In this case \(a_{1,j} = 0\) for all j such that \(1 < j \le n\). Since G is a tournament this implies \(a_{j,1} = 1\) for all such j. Then all the entries in the first column of A are 1. Also since A is the augmented adjacency matrix of G, \(a_{j,j} = 1\) for all \(j = 1, 2, \ldots, n\). Moreover, A satisfies consecutive 1's property for rows. Thus we have \(a_{j,i} = 1\) for all i such that \(1 \le i \le j\), for all \(j = 1, 2, \ldots, n\). Finally since G is a tournament \(a_{i,j} = 0\) for all i < j, for all \(j = 1, 2, \ldots, n\). Therefore A is the lower triangular matrix P with all entries 1 on and below the principal diagonal.

The converse part is obvious from the structure of \(A^*(G)\) as both the matrices described in the statement have consecutive 1's property for rows and for each pair \(i \neq j\), \(a_{i,j} = 0\) if and only if \(a_{j,i} = 1\). Thus G is an ICD which is a tournament.

Figure 4: Augmented adjacency matrix A = A^∗ (G) of a proper ICD G (left), the row permuted matrix B obtained from A that satisfies MCA property (middle) and a proper ICD representation of G (right).

5. Proper interval catch digraph

Let G = (V, E) be a simple digraph. Then the augmented adjacency matrix A^∗ (G) has a monotone consecutive arrangement (MCA) [2] if and only if it has independent row and column permutations such that 1's appear consecutively in each row and 1¹ ≤ 2¹ ≤ . . . ≤ n¹ and 1² ≤ 2² ≤ . . . ≤ n² where |V | = n and the values i¹ and i² denote the initial column and final column containing 1's in the i-th row. Now one can seperate the 1's and 0's by drawing upper and lower stairs (polygonal path from top left to bottom right) as in Figure 4 (right). In the following we give an adjacency matrix characterization of a proper ICD.

Theorem 5.1. Let G = (V, E) be a simple digraph. Then G is a proper ICD if and only if there exists a vertex ordering {v1, v2, . . . , vn} of V with respect to which the augmented adjacency matrix A^∗ (G) satisfies the following conditions:

• (1) A^∗ (G) satisfies consecutive 1's property for rows.
• (2) For i 6= j, if i¹ < j¹ then i² ≤ j² where i¹ and i² be the first and last column numbers containing 1 in the i-th row where 1 ≤ i ≤ n in A^∗ (G).

Proof. Let G = (V, E) be a proper ICD with representation {(Iⁱ , pi) | i = 1, 2, . . . , n} where V = {v1, v2, . . . , vn}, Iⁱ = [aⁱ , bⁱ ] and pi's are distinct for i = 1, 2, . . . , n. Then arranging the vertices according to increasing order of pi's we have consecutive 1's property for rows in A^∗ (G) = (ai,j ). We note that for i 6= j, ai,j = 1 if and only if viv^j ∈ E if and only if p^j ∈ Iⁱ if and only if i¹ ≤ j ≤ i² by definition.

Now for i 6= j suppose i¹ < j¹ and i² > j² hold simultaneously in A^∗ (G). Then pⁱ¹ ∈/ I^j as i¹ < j1. Again i¹ < j¹ ≤ j implies pⁱ¹ < p^j1 ≤ p^j . Since p^j ∈ I^j , the interval I^j lies entirely right to pⁱ¹ . So we get aⁱ < pⁱ¹ < a^j . As the intervals do not contain other properly we have bⁱ < b^j . Now as pⁱ² ∈ Iⁱ and pⁱ² > p^j (for i² > j² ≥ j) we get a^j ≤ p^j < pⁱ² < bⁱ < b^j . Then pⁱ² ∈ I^j which is a contraction as i² > j2. Hence i² ≤ j2. 3

³Note that, it follows from the condition (2) that "for i 6= j, i² < j² implies i¹ ≤ j1". For otherwise, let i² < j² and i¹ > j1. Then by the condition (2), we have j² ≤ i² (as j¹ < i1) which is a contradiction.

Conversely, let G satisfy conditions (1) and (2). We permute the rows of A = A^∗ (G) = (ai,j ) according to the non-decreasing order of i1's keeping the columns intact (see Figure 4). If there exist pair of rows i, j for which i¹ = j1, then place i-th row prior to j-th row when i² < j2. If i¹ = j¹ and i² = j² then keep i-th row prior to j-th row only when i < j in A. Let us call the modified matrix by B = (bi,j ). As A satisfies (2), after permuting only the rows of A it is easy to check that B satisfies MCA. Moreover permutation of rows of A does not affect the adjacency of the graph G, i.e., if i-th row of A is shifted to k-th row in B, then

\[a_{i,j} = 1\] if and only if \(b_{k,j} = 1\). (5.1)

Step 1. We show that the diagonal entries of the matrix B must be 1.

Suppose the i-th row of B was the k-th row of A. If k = i then bi,i = 1 as ai,i = 1. Suppose k > i in A. For each j = 1, 2, . . . , i, j¹ ≤ j ≤ i. Now the k-th row of A moved upward to the i-th row position in B. This implies there exists at least one such j so that k¹ ≤ j1. Then k¹ ≤ i < k ≤ k2. Hence ak,i = 1 which implies bi,i = 1. Again if k < i in A then there exists at least one j ≥ i such that j¹ < k¹ or, j¹ = k¹ and j² < k2. Then by the condition (2), in either case, we have j² ≤ k2. Thus k¹ ≤ k < i ≤ j ≤ j² ≤ k2. This implies ak,i = 1 and hence bi,i = 1.

Step 2. Defining intervals Iⁱ = [lⁱ , rⁱ ] for the i-th row of B.

Now we associate natural numbers in increasing order on the upper stair of B starting from the left top of it. Let bⁱ be the number on the stair in the i-th row where the stretch of consecutive 1's ends and aⁱ be the number on the stair in the i-th column where the stretch of consecutive 1's begins (e.g., in Figure 4, aⁱ = 1, 2, 4, 6, 8 and bⁱ = 3, 5, 7, 9, 10 for i = 1, 2, 3, 4, 5 respectively). Let i^o and i^e denote the first and last column numbers containing 1 in the i-th row of B (similar to the construction of i¹ and i² in A). Then by definition of aⁱ and bⁱ we have bⁱ > a^j for all i^o ≤ j ≤ ie. ⁴ Thus

\[b_{i,j} = 1 \Longrightarrow b_i > a_j. \tag{5.2}\]

Let kⁱ = max {j | j^o = io}. We assign interval Iⁱ = [lⁱ , rⁱ ] where

\[l_i = a_{i_o} + \frac{i - i_o}{k_i - i_o + 1}\] and \(r_i = b_i\).

By (5.2), bⁱ > a^io and so bⁱ ≥ a^io + 1 > lⁱ . Thus lⁱ < rⁱ for all i = 1, 2, . . . , n. Also since B satisfies MCA, one can check that lⁱ < l^j and rⁱ < r^j for all i < j. Therefore the set of intervals [li , rⁱ ] gives proper representation.

Step 3. Defining points p^j for each column j of B (as well as of A).

Let S^j = {lⁱ | i ≥ j, bi,j = 1}. Note that S^j 6= ∅ as bj,j = 1. Assign p^j = max {a^j , max Sj}.

Now p^j ≥ l^j as l^j ∈ S^j . Suppose for some i ≥ j, bi,j = 1. Then i^o ≤ j ≤ i^e which implies a^io ≤ a^j . So lⁱ < a^io + 1 ≤ a^j + 1 ≤ b^j . Also since bj,j = 1 by Step 1, we have a^j < b^j by (5.2). Thus p^j < b^j . Hence

\[p_j \in [l_j, r_j]. \tag{5.3}\]

⁴For example, in Figure 4, for i = 2, a^2o = 1, a^2e = 4 and b² = 5; for i = 3, a^3o = 2, a^3e = 6 and b³ = 7; etc.

Step 4. We show that bi,j = 1 if and only if p^j ∈ Iⁱ .

Case (i). bi,j = 1 and i > j.

By definition of S^j , lⁱ ∈ S^j and so p^j ≥ lⁱ . Again by (5.3), p^j ≤ r^j < rⁱ (as i > j). Thus p^j ∈ [lⁱ , rⁱ ] = Iⁱ .

Case (ii). bi,j = 1 and i < j.

As i < j, lⁱ < l^j ≤ p^j . Also since bi,j = 1, by (5.2), rⁱ = bⁱ > a^j which implies rⁱ ≥ a^j + 1. Moreover, for all t > j with bt,j = 1, l^t < a^j + 1 as in Step 3. Thus p^j < a^j + 1 ≤ rⁱ . Hence p^j ∈ [lⁱ , rⁱ ] = Iⁱ .

Case (iii). bi,j = 0 and i > j.

We first show that a^j ≤ p^j < a^j + 1. By definition of p^j , if p^j = a^j , then the claim is true. If p^j = max S^j , then again by definition p^j ≥ a^j . In this case, p^j = l^x for some x ≥ j such that bx,j = 1. Now bx,j = 1 implies x^o ≤ j and so a^xo ≤ a^j . By definition a^xo ≤ l^x < a^xo + 1. Then p^j = l^x < a^xo + 1 ≤ a^j + 1 as required.

In this case, the {i, j}-th position is left to (or, below) the lower stair, i.e., j < io. So a^j < a^io which implies a^j + 1 ≤ a^io . Then by the above argument, p^j < a^j + 1 ≤ a^io ≤ lⁱ (by definition of li). Thus We have p^j < lⁱ . Hence p^j ∈/ [lⁱ , rⁱ ] = Iⁱ .

Case (iv). bi,j = 0 and i < j.

The position {i, j} is right to (or, above) the upper stair. Hence bⁱ < a^j . But then rⁱ = bⁱ < a^j ≤ p^j . So p^j lies right to the interval [lⁱ , rⁱ ] = Iⁱ . Thus p^j ∈/ Iⁱ .

Step 5. Finally we show that p^j belongs to the interval corresponding to the vertex v^j . Note that, if the j-th row of A is shifted to the k-th row of B, then the vertex v^j corresponds to the interval Ik. Now by (5.1), we have bk,j = 1 as aj,j = 1. Then p^j ∈ I^k by Cases (i) and (ii) of Step 4.

This completes all the verifications. Therefore G is a proper ICD with respect to the above representation.

An unit interval catch digraph (in brief, unit ICD) is an ICD where every interval has the same length. We note the following result without proof as it goes with the same line as the proof of (1) ⇐⇒ (2) in Theorem 2.1 (see [3]).

Proposition 5.2. Let G be an ICD. Then G is a proper ICD if and only if it is a unit ICD.

Finally we define a digraph as proper oriented interval catch digraph (in brief, proper oriented ICD) if it is an oriented ICD where no two intervals are contained in other properly. Hence from Theorem 2.2 and Theorem 5.1 we get the following:

Theorem 5.3. Let G = (V, E) be an oriented graph. Then G is a proper oriented ICD if and only if there exists a vertex ordering which satisfy the following

for \[u < v < w\], if \(uw \in E\) then \(uv, vw \in E\) and if \(wu \in E\) then \(wv, vu \in E\). (5.4)

Proof. Let G = (V, E) be a proper oriented ICD. Then by Theorem 5.1, there exists an ordering of V that satisfies conditions (1) and (2). Let u < v < w be three vertices of V in this ordering

and uw ∈ E. Suppose u, v, w correspond to rows i, j, k respectively in A^∗ (G) = (ai,j ), where i < j < k. Since the matrix is augmented, ai,i = 1. Also uw ∈ E implies ai,k = 1. Thus by consecutive 1's property for rows, we have ai,j = 1 which implies uv ∈ E. Now the digraph is oriented. Thus aj,i = ak,i = 0. Then j¹ > i ≥ i1. Thus by condition (2), j² ≥ i2. But ai,k = 1 and so i² ≥ k. Then j² ≥ k which implies aj,k = 1. Hence vw ∈ E. The other part can be proved similarly.

Conversely, let G = (V, E) be an oriented graph satisfying the given condition. By Theorem 2.2, it follows that G is an ICD and so it satisfies the condition (1) of Theorem 5.1. Suppose in A∗ (G) = (ai,j ), i¹ < j¹ for two distinct rows i, j. Now if we can show that aj,i² = 1, then it follows that i² ≤ j² as required. If i² ≤ j, then i² ≤ j² as j ≤ j2. Let i² > j. If i < j, then i < j < i² and ai,i² = 1. Then by the given condition (first part), we have aj,i² = 1. Now if i > j, then i¹ < j¹ ≤ j < i and ai,i¹ = 1. Thus by the given condition (second part), we have aj,i¹ = 1. But this implies j¹ ≤ i¹ which is a contradiction.

Remark 5.4. It follows from the proof of the converse part of the above theorem that in the case of a proper oriented ICD G, A^∗ (G) itself satisfies MCA which may not be true for a proper ICD, in general.

6. Conclusion

In this paper we consider three subclasses of the class of ICD, namely central ICD, oriented ICD and proper ICD. We obtain characterizations for central ICD, oriented ICD when it is a tournament and proper ICD. In the following we show relationships between these digraphs in Figure 5 whose proofs follow from these characterization theorems. Several combinatorial optimization problems remain open for these digraphs, for example, to find the complete list of forbidden digraphs or to construct recognition algorithms for them.

Figure 5: Examples of relations between some subclasses of ICD

Acknowledgement

We are grateful to learned referees for their valuable suggestions and corrections which definitely improved and enhanced the paper. This research is partially supported by Jadavpur University under RUSA 2.0 Scheme (R-11/742/19 dated 27.06.2019) to the second author and partially by UGC (University Grants Commission) NET fellowship (21/12/2014(ii)EU-V) of the first author.

References

• [1] J. Bang-Jensen and G.Z. Gutin, Digraphs, Springer Monographs in Mathematics, 2008.
• [2] A. Basu, S. Das, S. Ghosh, and M. Sen, Circular-arc bigraphs and its subclasses, J. Graph Theory 73 (2013), 361–376. https://doi.org/10.1002/jgt.21681
• [3] K.P. Bogart and D.B. West, A Short Proof that Proper = Unit, Discrete Mathematics 201 (1999), 21–23. https://arxiv.org/pdf/math/9811036.pdf
• [4] E. Ceyhan, Domination number of an interval catch digraph family and its use for testing uniformity, Statistics 54 (2020), 310–339. https://doi.org/10.1080/02331888.2020.1720020
• [5] E. Ceyhan, Density of a random interval catch digraph family and its use for testing uniformity, REVSTAT 14 (2016), 349-394.
• [6] E. Ceyhan, The distribution of the relative arc density of a family of interval catch digraph based on uniform data, Metrika 75 (2012), 761-793. https://doi.org/10.1007/s00184-011- 0351-y
• [7] A. Das, S. Das, and M. Sen, Forbidden substructure for interval digraphs/bigraphs, Discrete Math. 339 (2016), 1028-1051. https://doi.org/10.1016/j.disc.2015.10.010
• [8] M.C. Golumbic, Algorithmic graph theory and perfect graphs, Annals of Disc. Math. 57, Elsevier Sci., USA, 2004.
• [9] P. Hell, R. Shamir, and R. Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM J. Comput. 31 (2001), 289-305. https://doi.org/10.1137/S0097539700372216
• [10] P. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl. 25 (1993), 15-25. https://doi.org/10.1016/0898-1221(93)90308-I
• [11] H. Maehara, A Digraph Represented by a Family of Boxes or Spheres, J. Graph Theory 8 (1984), 431–439. https://doi.org/10.1002/jgt.3190080312
• [12] D.S. Malik, M.K. Sen, and S. Ghosh, Introduction to Graph Theory, Cengage Learning Asia Pte Ltd, Singapore, 2014.

• [13] C. Priebe, D.J. Marchette, J.G. DeVinney, and D.A. Socolinsky, Classification using class cover catch digraphs, Journal of Classification 20 (2003), 3-23. https://doi.org/10.1007/s00357-003-0003-7
• [14] E. Prisner, A Characterization of Interval Catch Digraphs, Discrete Mathematics 73 (1989), 285-289. https://doi.org/10.1016/0012-365X(89)90271-9
• [15] M. Sen, S. Das, A.B. Roy, and D.B. West, Interval digraphs: An analogue of interval graphs, J Graph Theory 13 (1989), 189–202. https://doi.org/10.1002/jgt.3190130206