The strongly chordal graph literature has recently expanded to include the sequentially smaller classes of \(s\)-strongly chordal graphs for \(s = 1, 2, 3,\ldots\) (and the limiting class of majorly chordal graphs). These stronger classes preserve — while simultaneously intensifying — the conventional chords-of-cycles inspiration of chordal graph theory. This leads to characterizing corresponding \(s\)-strongly chordal bipartite graphs and majorly chordal bipartite graphs. Our new analysis does this by using chains of quadrangles, with each adjacent pair of quadrangles having a unique edge in common. This leads to constructive characterizations that exploit a somewhat unexpected resemblance to earlier characterizations of \(s\)-strongly chordal graphs involving chains of triangles sharing common edges to characterize \(s\)-strongly chordal tripartite (and, similarly, multipartite) graphs.
All graphs \(G\) here will be finite and simple. A cycle \(C\) is a \(^\ge\)\(n\)-cycle means it has length \(|E(C)| = |V(C)| \ge n\). A chord of a cycle \(C\) is an edge \(vw\) of \(G\) joining nonconsecutive vertices \(v\) and \(w\) of \(C\), with \(vw\) an \(i\)-chord of \(C\) if and only if \(v\) and \(w\) are distance \(i\) apart along \(C\) with \(2 \le i \le \frac{1}{2}|E(C)|\). Each \(i\)-chord of \(C\) is also called a \(^\ge\)\(h\)-chord of \(C\) whenever \(2 \le h \le i\). The chords, \(i\)-chords, and \(^\ge\)\(i\)-chords of a path \(\pi\) are similarly defined by simply replacing cycles with paths and \(C\) with \(\pi\) (but without \(\le \frac{1}{2}|E(\pi)|\) restrictions).
Define a graph to be chordal if and only if each \(^\ge\)\(4\)-cycle — so each cycle long enough to have a chord — does have a chord (a \(^\ge\)\(2\)-chord). See [4, 15] for terms not defined here and, in particular, for background on chordal graphs. [Chordal graphs have sometimes been called ‘triangulated graphs,’ in spite of that making trees ‘triangulated’ and making octahedral graphs not be ‘triangulated,’ since they have induced \(4\)-cycles.]
Define a graph to be strongly chordal if and only if it is chordal and each \(^\ge\)\(6\)-cycle — so each cycle long enough to also have a \(3\)-chord — does have a \(3\)-chord (and \(2\)-chords). Martin Farber [6] introduced strongly chordal graphs in 1983, along with many characterizations; [3] contains updated characterizations and applications.
Proposition 1.1 is a consequential characterization of strongly chordal graphs that will motivate the results of Section 2, and so of the rest of the paper; it can be viewed as a restatement of Dahlhaus, et al. [5, Thm. 1.2].
Proposition 1.1. [5] A chordal graph is strongly chordal if and only if each \(^\ge\)\(6\)-cycle \(C\) contains an edge that forms a triangle with two chords of \(C\).
We will also refer to strongly chordal graphs as 1-strongly chordal graphs (and, for convenience, think of chordal graphs as being ‘\(0\)-strongly chordal’). When \(s\ge 2\), define a graph to be \(s\)-strongly chordal if and only if, for each \(i \in \{2, \ldots, s+2\}\), each \(^\ge\)\(2i\)-cycle — so each cycle long enough to have an \(i\)-chord — does have an \(i\)-chord. See [11, 13, 14] for recent characterizations of being \(s\)-strongly chordal — and so for being majorly chordal graphs, which we define by being \(s\)-strongly chordal for all \(s \ge 1\).
In Section 2, we will modify the above for bipartite graph theory, ending with a characterization of strongly chordal bipartite graphs. In Section 3, we will similarly modify the \(s\)-strongly chordal graphs for bipartite graph theory, ending with characterizations of \(s\)-strongly chordal bipartite and majorly chordal bipartite graphs. Finally, Section 4 will consider how this approach resembles — while differing importantly from — the conventional notion of so-called ‘\(2\)-path’ graphs, followed by a few intriguing open questions.
Define a graph to be chordal bipartite if and only if it is bipartite and each \(^\ge\)\(6\)-cycle — so each cycle long enough to have a chord in a bipartite graph — does have a chord (a \(^\ge\)\(3\)-chord). M. C. Golumbic [7] introduced chordal bipartite graphs in 1978, along with several characterizations and applications; see [4, 15]. As the graph \(C_4\) shows, chordal bipartite graphs do not need to be chordal — paralleling \(C_4\) being called a ‘complete bipartite graph’ without being a complete graph. (Note that cycles of a bipartite graph always have even lengths, while \(i\)-chords of bipartite graphs always have odd \(i\) values.)
Proposition 2.1. [3] A graph is chordal bipartite if and only if it is triangle-free with no induced \(^\ge\)\(5\)-cycles — equivalently, if and only if it is bipartite and each \(^\ge\)\(6\)-cycle has a \(3\)-chord.
Define a chordal bipartite graph to be strongly chordal bipartite if and only if each \(^\ge\)\(10\)-cycle — so each cycle long enough to have a \(5\)-chord — does have a \(5\)-chord (and \(3\)-chords). Strongly chordal bipartite graphs were introduced in [7]; also see [2, 8, 9, 16].
The following paragraphs will introduce notions that will be fundamental to Lemma 2.2, and so to the rest of this paper. Two chords \(ab\) and \(cd\) are crossing chords of a cycle \(C\) (or of a path \(\pi\)) if and only if their four endpoints come in the order \(a,c,b,d\) around \(C\) (respectively, along \(\pi\)) — otherwise they are noncrossing chords of \(C\) (or \(\pi\)).
For \(r \ge 1\), define an \(r\)-quadrangle \(2\)-bipath graph to consist of a \((2r+2)\)-cycle \(C\) with exactly \(r-1\) noncrossing chords that combine to produce \(r\) quadrangles (\(4\)-cycles) in a bipartite graph, as shown in Figure 1. The \(2\)-quadrangle \(2\)-bipath subgraphs are often called ‘domino’ subgraphs, and the \(1\)-quadrangle \(2\)-bipath subgraphs are the \(C_4\) subgraphs. (A graph’s edges — its \(K_2\) subgraphs — could be thought of as its \(0\)-quadrangle \(2\)-bipaths.)
The terminology ‘\(2\)-bipath’ is meant to be the bipartite analog of ‘\(2\)-path’ in [17], which involved triangles (instead of quadrangles) that are ‘adjacent’ precisely when they have a unique edge in common. [The role of \(2\)-paths in chordal nonbipartite graph theory will be the topic of Section 4; also see [1].]
Call the two ‘end quadrangles’ of a \(^\ge\)\(2\)-quadrangle \(2\)-bipath its terminal quadrangles; each consists of three edges of the spanning cycle \(C\) and one chord of \(C\). Each nonterminal quadrangle consists of two edges in \(E(C)\) and two noncrossing chords of \(C\). Thus, an \(r\)-quadrangle \(2\)-bipath consists of a total of \(2r+2\) edges in \(E(C)\) and \(r-1\) noncrossing chords of \(C\). Figure 1 shows two examples of \(r\)-quadrangle \(2\)-bipaths.
Lemma 2.2. A chordal bipartite graph \(G\) is strongly chordal bipartite if and only if each \(^\ge\)\(10\)-cycle \(C\) of \(G\) has a length-\(5\) subpath that combines with two noncrossing chords of \(C\) to form a \(2\)-quadrangle \(2\)-bipath of \(G\).
Proof. Suppose \(G\) is a chordal bipartite graph with an arbitrary \(^\ge\)\(10\)-cycle \(C\).
For the ‘only-if-implication’\(\!\), assume \(G\) is strongly chordal bipartite, and so \(C\) has a \(5\)-chord \(vw\). Let \(C'\!\) denote the \(6\)-cycle formed by combining the length-\(5\) \(v\)-to-\(w\) subpath \(\pi\) of \(C\) with the edge \(vw\). Since \(C'\!\) has a \(3\)-chord (call it \(v'w'\)) by Proposition 2.1, the length-\(5\) subpath \(\pi\) of \(C\) combines with the two noncrossing chords \(vw\) and \(v'w'\) of the path \(\pi\) to form a \(2\)-quadrangle \(2\)-bipath subgraph of \(G\) that is spanned by \(C\).
For the converse ‘if-implication’\(\!\), assume \(C\) has a length-\(5\) subpath together with \(2\) noncrossing chords that form a \(2\)-quadrangle \(2\)-bipath, one of which is a \(3\)-chord with the other a \(5\)-chord of the \(^\ge\)\(10\)-cycle \(C\). Since this arbitrary \(^\ge\)\(10\)-cycle \(C\) has a \(5\)-chord, the induced subgraph \(G[V(C)]\) of \(G\) — and so the graph \(G\) itself — is a strongly chordal bipartite by definition. ◻
Whenever \(s \ge 1\), define a bipartite graph to be \(s\)-strongly chordal bipartite if, for each odd \(i \in \{3, 5, \ldots, s+3\}\), each \(^\ge\)\(2i\)-cycle — so each cycle long enough to have such an \(i\)-chord — does have an \(i\)-chord. Equivalently, a graph \(G\) is \(s\)-strongly chordal bipartite for \(s \ge 1\) if and only if \(G\) is bipartite and \((s-1)\)-strongly chordal and each length \(^\ge\)\(2(s+3)\)-cycle \(C\) has an \((s+3)\)-chord. (And being \(1\)-strongly chordal bipartite is equivalent to being strongly chordal bipartite).
Theorem 3.1. When \(s \ge 2\), an \((s-1)\)-strongly chordal bipartite graph \(G\) is \(s\)-strongly chordal bipartite if and only if each \(^\ge\)\((4s+6)\)-cycle \(C\) of \(G\) has a length-\((2s+3)\) subpath that combines with \(s+1\) of its noncrossing chords of \(C\) to form an \((s+1)\)–quadrangle \(2\)-bipath of G.
Figure 2 is intended to help in picture both directions of its inductive proof as written below. It shows the proof’s spanning cycle \(C\) (but with only some of its vertices and possible chords shown). Cycle \(C_1\) starts at the left end of \(C\) and ends with the chord \(v_{\ell}w_r\) of \(C\) — which is one of the three possible chords shown as dotted edges — and is central to the proof. The path \(\pi_1\) will be the length-\((2s+3)\) subpath of \(C_1\) that connects \(v_{\ell}\) and \(w_r\). Note that a chord \(v_iw_i\) of \(C\) is an \(i\)-chord of \(C\) if and only if \(3 \le i \le \big\lfloor{s/2}\big\rfloor\). Cycle \(C_2\) starts at the chord \(v_{2s+1}w_{2s+1}\) of \(C\) and continues around the right end of \(C\) (so \(v_{\ell}w_r\) is a chord of \(C_2\)). [The proof’s ultimate \((s+1)\)-quadrangle \(2\)-bipath will be formed by the edges of \(\pi_1\) and the noncrossing chords \(v_3w_3\), \(v_5w_5, \ldots,\!\) \(v_{2s+1}w_{2s+1},\!\) \(v_{\ell}w_r\) of \(\pi_1\).]
Proof. Suppose \(s \ge 2\) and \(G\) is \((s-1)\)-strongly chordal bipartite [arguing by induction on \(s\)]. The \(s = 2\) inductive step follows from Lemma 2.2.
For the ‘only-if-implication’ inductive step, assume \(G\) is \(s\)-strongly chordal bipartite and \(s \ge 3\), with \(C\) an arbitrary \(^\ge\)\((4s+6)\)-cycle [toward showing that \(G\) has an \((s+1)\)-quadrangle \(2\)-bipath subgraph as described in the theorem].
By the \([s-1]\) inductive hypothesis and \(4s+6 > 4[s-1]+6 = 2(2s+1)\), cycle \(C\) has a length-\((2s+1)\) subpath (call it \(\pi_1\)) whose end vertices (call them \(v_{\ell}\) and \(w_r\)) are adjacent in \(G\). Label the vertices to make \(\pi_1 = (v_{\ell},\ldots,\!\) \(v_3,\!\) \(v_2,\!\) \(w_2,\!\) \(w_3,\!\) \(\ldots,w_r)\) where the sequences \((\ell,\ldots,3)\) and \((3,\ldots,r)\) of subscripts consist of, respectively, \(\ell – 2\) decreasing and \(r-2\) increasing odd integers, allowing \(v_i = v_j\) if \(v _i = v_{i'} = v_j\) when \(i \le v' \le j\) (and similarly for vertices \(w_i = w_j\)).
Deleting the \(2s\) vertices in \(V(\pi_1) \setminus \{v_\ell, w_r\}\) from \(C\) leaves an induced \(s\)-strongly chordal bipartite subgraph of \(G\) that is spanned by a cycle (call it \(C_2\)) of edges in \(E(C) \cup \{v_{2s+1}w_{2s_1}\}\). By Lemma 2.2, \(C_2\) has a \(3\)-chord (call it \(vw\)) that combines with the chord \(v_{2s+1}w_{2s+1}\) and two edges in \(E(C_2)\) to form a quadrangle; this shows \(v_\ell w_r \in \{v_{2s+1}w_{2s+3},\!\) \(v_{2s+2}w_{2s+2},\!\) \(v_{2s+3}w_{2s+1}\}\).
Therefore, the length-\((2s+3)\) subpath \(\pi_1\) combines with the \(s+1\) noncrossing chords \(v_3w_3, v_5w_5, \ldots,\!\) \(v_{2s+1}w_{2s+1},\!\) \(vw\) of \(\pi_1\) to form an \((s+1)\)-quadrangle \(2\)-bipath subgraph [as the theorem requires].
For the ‘if-implication’ inductive step, assume \(C\) is an arbitrary \(^\ge\)\((4s+6)\)-cycle of the \((s-1)\)-strongly chordal bipartite graph \(G\) [toward showing that \(C\) has a \((2s+3)\)-chord, which will show that \(G\) is \(s\)-strongly chordal bipartite (as noted in the second sentence of §3)].
By the \([s-1]\)inductive hypothesis and \(2[s-1]+3 = 2s+1\), cycle \(C\) has a \((2s+1)\)-chord (call it \(v_{2s+1}w_{2s+1}\)). Now — much as was done in the preceding only-if-implication proof — let \(C_1\) denote the \((2s+1)\)-cycle formed by \(v_{2s+1}w_{2s+1}\) and the subpath \(\pi_1 = (v_{2s+1},\ldots,\!\) \(v_3,\!\) \(v_2,\!\) \(w_2,\!\) \(w_3,\ldots,w_{2s+1})\), and let \(C_2\) be the cycle with edge set \(\{v_{2s+1}w_{2s+1}\} \cup E(C) \setminus E(\pi_1)\). By the inductive hypothesis, \(C_2\) has a \(3\)-chord \(v_\ell w_r\) that combines with \(v_{2s+1}w_{2s+1}\) and two additional edges in \(E(C_2)\) to form a quadrangle. Therefore — since \((2s+1)\)-chord \(v_{2s+1}w_{2s+1}\) of \(C\) is an edge of \(C_1\) and \(|E(C)| \ge 4x+6 = |E(C_1)| + 2\) — the edge \(v_\ell w_r \in E(C_1) \setminus E(C_2)\) is a \((2s+3)\)–chord of \(C\) [as foreseen in the preceding paragraph]. ◻
Note that, since cycles of bipartite graphs can only have \(i\)-chords when \(i\) is odd, every cycle length must be divisible by \(2\) but not by \(4\) — in other words, when \(i\) is oddly even (occasionally called ‘singly even’)— so whenever \(i = 2, 6, 10, \cdots\).
Corollary 3.2. A chordal bipartite graph \(G\) is majorly chordal bipartite if and only if each oddly even cycle spans a quadrangle \(2\)-bipath of \(G\).
Proof. This follows from Theorem 3.1. ◻
The preceding sections concerning bipartite graphs are, in hindsight, unexpectedly similar to what happens for ‘arbitrary’ (meaning not necessarily bipartite) graphs. In particular, using quadrangle \(2\)-bipaths for \(s\)-strongly chordal bipartite graphs closely resembles the role of ‘triangle \(2\)-paths’ for \(s\)-strongly chordal (but otherwise arbitrary) graphs, as presented in [13] and defined below. The prefix in ‘\(2\)-bipaths’ and ‘\(2\)-paths’ emphasizes that the quadrangles (respectively, triangles) are adjacent if and only if they share exactly \(2\) vertices, and they induce a complete subgraph (in other words, they form an edge) each of which is in at most two of the quadrangles (or triangles).
For \(r \ge 1\), define an \(r\)-triangle \(2\)-path graph to consist of an \((r+2)\)-cycle \(C\) with exactly \(r-1\) noncrossing chords that combine to produce \(r\) triangles (\(3\)-cycles) in an arbitrary graph, as illustrated in Figure 3.
Call the two end triangles of a \(^\ge\)\(2\)-triangle \(2\)-path its terminal triangles; each consists of two edges of the spanning cycle \(C\) together with one chord of \(C\). Each nonterminal triangle consists of one edge in \(E(C)\) and two noncrossing chords of \(C\). Thus, an \(r\)-triangle \(2\)-path consists of a total of \(r+2\) edges in \(E(C)\) and \(r-1\) noncrossing chords of \(C\). Figure 3 shows two examples of \(r\)-triangle \(2\)-paths.
The following two results can be used to illustrate how Theorem 3.1 and Corollary 3.2, for bipartite graphs, correspond to results for arbitrary graphs. Proposition 4.1 is basically [13, Thm. 2] (it also follows from the description of \(r\)-triangle \(2\)-paths given above, and then emulating the proof of Theorem 3.1 from Section 3). Similarly, Corollary 4.2 will correspond to Corollary 3.2.
Recall that an \(s\)-strongly chordal graph is simply a chordal graph such that, for each even \(i \in \{2, \ldots, s+2\}\), each \(^\ge\)\(2i\)-cycle has an \(i\)-chord. Equivalently, a graph \(G\) is \(s\)-strongly chordal for \(s \ge 2\) if and only if it is \((s-1)\)-strongly chordal and each \(^\ge\)\(2(s+2)\)-cycle \(C\) has an \((s+2)\)-chord. (Indeed, the condition ‘each \(^\ge\)\(2(s+2)\)-cycle’ can be simplified to ‘each \(2(s+2)\)-cycle’ [13].)
Proposition 4.1([13]). When \(s \ge 1\), an \((s-1)\)-strongly chordal graph \(G\) is \(s\)-strongly chordal if and only if each \(^\ge\)\((2s+4)\)-cycle \(C\) of \(G\) has a length-\((s+2)\) subpath that combines with \(s+1\) of its noncrossing chords of \(C\) to form an \((s+1)\)-triangle \(2\)-path of \(G\).
Corollary 4.2. A chordal graph \(G\) is majorly chordal if and only if each even cycle spans a triangle \(2\)-path of \(G\).
The similar strengthenings of chordal graphs in Theorem 3.1 and chordal bipartite graphs in Proposition 4.1 both appeared — with somewhat different wordings — in [10]. Note how, as \(s\) increases, both of these strengthenings ultimately end with their maximum-size (bi)graphs being (respectively) the complete (bipartite) graphs. The following section will briefly consider how these natural extensions can be strengthened to chordal \(n\)-partite graphs.
Recall that an \(n\)-partite graph can be defined by being able to partition its vertices into \(n \ge 2\) independent ‘partition sets’ (sometimes called ‘color classes’), with the endpoints of each of its edges in separate partition sets — so \(2\)-partite means bipartite, \(3\)-partite means tripartite, and so on.
Whenever \(s \ge 2\), define an \(n\)-partite graph to be \(s\)-strongly chordal \(n\)-partite if, for each \(i \in \{1,2, \ldots, s+2\}\), each \(^\ge\)\(2i\)-cycle — so each cycle long enough to have such an \(i\)-chord — does have an \(i\)-chord. (And, of course, being 1-strongly chordal \(2\)-partite is equivalent to being strongly chordal bipartite.)
For \(r \ge 1\) and \(n \ge 3\), define an \(r\)–\(\langle n\)-cycle\(\rangle\) \(2\)-path of a graph \(G\) to consist of an \((r+2)\)-cycle \(C\) of \(G\) that combines with \(r-1\) noncrossing chords of \(C\) to form \(r\) many \(n\)-cycles (\(n\)-gons) of a graph. Thus, the \((s+1)\)-triangle \(2\)-paths in Proposition 4.1 become the \((s+1)\)–\(\langle\)\(3\)-cycle\(\rangle\) \(2\)-paths, and the \((s+1)\)-quadrangle \(2\)-paths in Theorem 3.1 become the \((s+1)\)–\(\langle 4\)-cycle\(\rangle\) \(2\)-paths.
Everything done with quadrangular \(2\)-bipaths in Figures 1 and 2 and with triangular \(2\)-paths in Figure 3 can be emulated for \(n\)-cycle \(2\)-paths that span cycles \(C\) in which each of the two terminal \(n\)-cycles consists of \(n-1\) edges of \(C\) and one chord of \(C\), and each of the \(r-2\) nonterminal \(n\)-cycles consists of \(n-2\) edges of \(C\) and two noncrossing chords of \(C\). An \(r\)–\(\langle n\)-cycle\(\rangle\) \(2\)-path consists of a total of \(2(n-1) + (r-2)(n-2) = rn-2r+2\) edges in \(E(C)\) and \((2\cdot1 + [r-2]\cdot2)/2 = r-1\) noncrossing chords of \(C\).
Theorem 5.1. When \(s,n \ge 3\), an \((s-1)\)-strongly chordal \(n\)-partite graph is \(s\)-strongly chordal \(n\)-partite if and only if each \(^\ge\)\((4s+6)\)-cycle has a length-\((2s+3)\) subpath that combines with \(s+1\) of its noncrossing chords to form an \((s+1)\)–\(\langle n\)-cycle\(\rangle\) \(2\)-path.
Proof. This follows from the comments and formulas in the preceding paragraph, along with replacing ‘bipartite’ with ‘\(n\)-partite’ and ‘quadrangle’ with ‘\(\langle n\)-cycle\(\rangle\),’ in the inductive proof of Theorem 3.1 for \(s \ge 1\). ◻
Corollary 5.2. A strongly chordal \(n\)-partite graph is majorly chordal if and only if each even cycle spans an \(\langle n\)-cycle\(\rangle\) \(2\)-path.
Proof. This follows from Theorem 5.1 (and corresponds to Corollary 3.2). ◻
The Theorem 5.1 (and Corollary 5.2) characterizations involve the existence of paths of \(n\)-gons for each \(n \in \{3, 4, \ldots, s\}\) (and \(s = \infty\)). There are also unexpected opportunities, problems, and consequences when utilizing \(n\)-partite graphs with \(n \ge 2\).
For instance, how well is chordal graph theory reflected among chordal bipartite graphs? The following dates from [6, Thm. 4.1] (also see [12]): A chordal graph is strongly chordal if and only if the uncrossed chords of each cycle are independent (meaning that no subset of them forms a cycle). But what could the strongly chordal bipartite counterpart of independence be beyond \(n = 3\)? (Might this simply reflect the lack of a simple forbidden induced subgraph characterization for \(^\ge\)\(2\)-partite graphs?)
Recall how Proposition 4.1 and Corollary 4.2 show very similar structures for the \(s\)-strongly chordal graphs and the \(s\)-strongly chordal bipartite graphs from Theorem 3.1 and Corollary 3.2 — in other words, the \(s\)-strongly chordal \(n\)-partite graph classes when \(n \in \{1,2\}\). But now, Theorem 5.1 and Corollary 5.2 unexpectedly show even more closely-related structures for the \(s\)-strongly chordal \(n\)-partite graph classes whenever \(n \ge 2\) (despite \(2\)-paths of \(n\)-gons being \(s\)-strongly chordal \(n\)-partite graphs without being \((n-1)\)– or \((n+1)\)-partite). Is there is anything else that Theorem 3.1 (for bipartite graphs and their quadrangle \(2\)-bipaths) might suggest — beyond Theorem 5.1 and Corollary 5.2 — about \(2\)-paths of pentagons (or of \(^\ge\)\(3\) \(n\)-gons)?