Forbidden paths and cycles in the undirected underlying graph of a 2-quasi best match graph Annachiara Korchmaros Bioinformatics Group, Department of Computer Science & Interdisciplinary Center for Bioinformatics, UniversitΓ€t Leipzig, HΓ€rtelstraße 16–18, D-04107 Leipzig, Germany. Abstract The undirected underlying graph of a 2-quasi best match graph (2-qBMG) is proven not to contain any induced graph isomorphic to 𝑃6 or 𝐢6 . This new feature allows for the investigation of 2-BMGs further by exploiting the numerous known results on 𝑃6 and 𝐢6 free graphs together with the available polynomial algorithms developed for their studies. In this direction, there are also some new contributions about dominating bicliques and certain vertex decompositions of the undirected underlying graph of a 2-qBMG. Keywords Phylogenetic combinatorics, quasi best match graphs, 𝑃6 - and 𝐢6 -free graphs, dominating set, vertex decomposition. 1. Introduction by three types of forbidden induced subgraphs, called of types (𝐹1 ), (𝐹2 ) and (𝐹3 ); see Section 2. Quasi-best match graphs are directed vertex-colored This investigation focuses on specific properties of graphs explained by phylogenetic trees. A tree-free char- the underlying undirected graph of a 2-qBMG. Actually, acterization is known so far for the case of two colors [1]: such undirected graphs have been touched so far only A two-color quasi best match graph (2-qBMG) is a bipar- marginally in the study of 2-qBMGs except in the very βƒ–βƒ— without loops and parallel edges tite directed graph 𝐺 special case of reciprocal 2-BMGs; see [9, 10]. The main which has the following three properties: motivation for this study is the richness of the literature on undirected graphs. It is indeed much richer than on (N1) if 𝑒 and 𝑣 are two independent vertices then there directed graphs, with plenty of fundamental works on exist no vertices 𝑀, 𝑑 such that 𝑒𝑑, 𝑣𝑀, 𝑑𝑀 are edges; forbidden configurations, decompositions, and vertex- (N2) bi-transitive, i.e., if 𝑒𝑣, 𝑣𝑀, 𝑀𝑑 are edges then 𝑒𝑑 is colorings, as well as on algorithms and valuations on also an edge; computational complexity. The aim is to exploit some of these deeper results on undirected graphs to gain new (N3) if 𝑒 and 𝑣 have common out-neighbor then either insights into 2-qBMGs. It may happen, however, that all out-neighbors of 𝑒 are also out-neighbors of 𝑣 going back to a digraph 𝐺 βƒ–βƒ— from its underlying undirected or all out-neighbors of 𝑣 are also out-neighbors graph 𝐺, a deep result on 𝐺 only has a very limited, or of 𝑒. βƒ–βƒ— Thus, the structural relationship even trivial impact on 𝐺. A 2-qBMG is a two-colored best match graph (2-BMG) if it between 𝐺 βƒ–βƒ— and 𝐺 is far to be immediate. For instance, [6, is sink-free, i.e., no vertex has empty out-neighborhood, Theorem 3.4] does not yield an analog characterization and it is a reciprocal two-best match graph (reciprocal 2- in terms of forbidden induced subgraphs of the under- BMG) if all its edges are symmetric. Moreover, 2-qBMGs lying undirected graph. This depends on the fact that but not 2-BMGs form a hereditary class [1]. the underlying undirected graph of a digraph of type (𝐹𝑖 ), 2-BMGs, 2-qBMGs, and more generally best match 1 ≀ 𝑖 ≀ 3 with only required edges is either a path of graphs have been the subjects of intensive studies, also length 4 or 5 but it is not necessarily a forbidden subgraph motivated by their relevant roles in the current investi- of the underlying undirected graph of a 2-qBMG. gation of orthology predictions from sequence similarity Therefore, the challenge is to find appropriate results in the case that the gene families histories are free from and knowledge on undirected graphs that may produce gene transfers; see [2, 3, 4, 1, 5, 6, 7, 8]. A major contribu- relevant contributions to the study of 2-qBMGs via their tion [6, Theorem 3.4] is a characterization of 2-qBMGs underlying undirected graphs. ITAT’24: Information technologies – Applications and Theory, The main results in this direction are Theorem 3.1 and September 20–24, 2024, Drienica, Slovakia Theorem 3.9, which state that the underlying undirected Envelope-Open annachiara.korchmaros@uni-leipzig.de (A. Korchmaros) graph of every 2-qBMG is 𝑃6 -free and 𝐢6 -free, that is, GLOBE https://akorchmaros.com/ (A. Korchmaros) both 𝑃6 and 𝐢6 are forbidden induced subgraphs. This Orcid 0000-0002-7334-669X (A. Korchmaros) result is sharp as the underlying undirected graph of a 2- Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). qBMG may have an induced path 𝑃5 (and hence induced CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings 𝑃4 as well); see Theorem 3.2. Therefore, the underlying and {𝑣2 , 𝑣4 , …}. An undirected graph is 𝑃𝑛 -free if it has undirected graphs of a type (𝐹𝑖 ) digraph, 1 ≀ 𝑖 ≀ 3, are no induced subgraph isomorphic to a 𝑃𝑛 path-graph. A not forbidden subgraphs for the underlying undirected cograph is a 𝑃4 -free graph. graph of 2-qBMGs. A cycle 𝐢𝑛 of an undirected graph 𝐺 is a sequence In their seminal paper [11] appeared in 1993, BacsΓ³ 𝑣1 𝑣2 β‹― 𝑣𝑛 𝑣1 of pairwise distinct vertices of 𝐺 such that and Tuza pointed out the strong relationship between 𝑣𝑖 𝑣𝑖+1 ∈ 𝐸(𝐺) for 𝑖 = 1, … , 𝑛 βˆ’ 1, and 𝑣𝑛 𝑣1 ∈ 𝐸(𝐺). A 𝐢𝑛 π‘ƒπ‘˜ -freeness and dominating subsets in undirected graphs. cycle-graph is an undirected graph on 𝑛 vertices with a Relevant contributions on such a relationship were given cycle 𝑣1 𝑣2 β‹― 𝑣𝑛 𝑣1 containing no chord, i.e. any edge in in several papers, especially in [12, 13, 14, 15, 16]. In par- 𝐸(𝐺) is either 𝑣𝑖 𝑣𝑖+1 ∈ 𝐸(𝐺) for some 1 ≀ 𝑖 ≀ 𝑛 βˆ’ 1, or ticular, for any bipartite graph 𝐺, Liu and Zhou proved 𝑣𝑛 𝑣1 . For 𝑛 even, a 𝐢𝑛 cycle-graph with a cycle 𝑣1 𝑣2 β‹― 𝑣𝑛 𝑣1 that 𝐺 is both 𝑃6 -free and 𝐢6 -free if and only if every con- containing no chord is a bipartite graph with (uniquely nected induced subgraph of 𝐺 has a dominating biclique; determined) color classes {𝑣1 , 𝑣3 , …} and {𝑣2 , 𝑣4 , …}. Bipar- see [15, Theorem 1]. An independent constructive proof tite cycle-graphs can only exist for even 𝑛. An undirected of the Liu-Zhou theorem is due to P. van’t Hof and D. graph is 𝐢𝑛 -free if it has no induced subgraph isomorphic Paulusma [14] where the authors also provide an algo- to an 𝐢𝑛 cycle-graph. rithm that finds such a dominating biclique of a connected A set 𝐷 βŠ† 𝑉 (𝐺) is a dominating set of an undirected 𝑃6 -free graph in polynomial time. For a discussion on the graph 𝐺 if, for any vertex 𝑒 ∈ 𝑉 (𝐺) ⧡ 𝐷, there is a vertex computational complexity of the problem of finding (not 𝑣 ∈ 𝐷 such that 𝑒𝑣 ∈ 𝐸(𝐺). We also say that 𝐷 dominates necessarily dominating) bicliques in undirected bipartite 𝐺. A subgraph 𝐻 of 𝐺 is a dominating subgraph of 𝐺 if graphs, see [17]. An upper bound on the number of bi- the vertex set of 𝐻 dominates 𝐺. cliques of 𝐢6 -free undirected bipartite graphs in terms An undirected graph 𝐺 is of type 𝐾 βŠ• 𝑆 if either 𝐺 is of the sizes of their color classes π‘ˆ , π‘Š is given in [18, degenerate, i.e. if it has an isolated vertex, or there is a Theorem 3.3] where it is shown that such number does partition of 𝑉 (𝐺) into two sets: a biclique set 𝐾 and a not exceed |π‘ˆ |2 |π‘Š |2 . stable set 𝑆; see [19, 20]. Recognition and optimization problems for both 𝑃6 For directed graphs 𝐺 βƒ–βƒ— with vertex-set 𝑉 (𝐺) βƒ–βƒ— and edge- and 𝐢6 -free bipartite undirected graphs and certain de- βƒ–βƒ— set 𝐸(𝐺), in particular for 2-qBMGs, notation and termi- compositions involving 𝐾 βŠ• 𝑆 graphs have been studied nology come from [1]. In particular, 𝑁 + (𝑣) and 𝑁 βˆ’ (𝑣) by several authors, following the paper [19]. In particular, stand for the set of out-neighbours and in-neighbours of it is shown that the class of both 𝑃6 and 𝐢6 -free bipartite 𝑣 in 𝐺,βƒ–βƒ— and 𝑣 is a sink when 𝑁 + (𝑣) = βˆ…, and 𝑣 is a source graphs can be recognized in linear time. Also, efficient when 𝑁 βˆ’ (𝑣) = βˆ…. A digraph 𝐺 βƒ–βƒ— is oriented if 𝑒𝑣 ∈ 𝐸(𝐺) βƒ–βƒ— im- solutions for two NP-hard problems are presented in this βƒ–βƒ— βƒ–βƒ— plies 𝑣𝑒 βˆ‰ 𝐸(𝐺) for any 𝑒, 𝑣 ∈ 𝑉 (𝐺). An oriented digraph class of graphs: the maximum balanced biclique problem has a topological vertex ordering if its vertices can be la- and the maximum independent set problem. For more βƒ–βƒ— we have beled with 𝑣1 , 𝑣2 , … such that for any 𝑣𝑖 𝑣𝑗 ∈ 𝐸(𝐺) details, see the recent paper [20]. 𝑖 < 𝑗. A sufficient condition for an oriented digraph to A contribution to the study of the vertex decomposi- have a topological ordering is to be acyclic, that is, there tion problem for 2-qBMGs in smaller connected 2-qBMGs is no directed cycle in the digraph. An orientation of a of type (A) is given in Theorem 4.2, where a connected βƒ–βƒ— is a digraph obtained from 𝐺 βƒ–βƒ— by keeping the 2-qBMG is of type (A) if its underlying undirected graph digraph 𝐺 is a 𝐾 βŠ• 𝑆 graph, that is, it has a vertex decomposition same vertex set but retaining exactly one edge from each into a (dominating) biclique 𝐾 and a stable set 𝑆, that is, symmetric edge. From [4, Lemma 2.2] and [4, Theorem any two vertices in 𝑆 are independent. 3.8], any orientation of a 2-qBMG is acyclic whenever at least one of the following conditions are satisfied: βƒ–βƒ— (βˆ—) no two (or more than two) symmetric edges of 𝐺 2. Background have a common endpoint; The notation and terminology for undirected graphs are βƒ–βƒ— are equiv- (βˆ—βˆ—) no two (or more than two) vertices of 𝐺 standard. Let 𝐺 be an undirected graph with vertex-set alent, i.e. no two vertices have the same in- and 𝑉 (𝐺) and edge-set 𝐸(𝐺). In particular, a path 𝑃𝑛 of an out-neighbors. undirected graph 𝐺 is a sequence 𝑣1 𝑣2 β‹― 𝑣𝑛 of pairwise dis- tinct vertices of 𝐺 such that 𝑣𝑖 𝑣𝑖+1 ∈ 𝐸(𝐺) for 𝑖 = 1, … , π‘›βˆ’1. Acyclic-oriented digraphs are odd–even graphs. For a A 𝑃𝑛 path-graph is an undirected graph on 𝑛 vertices with pair (𝔄, 𝔒) where 𝔄 is a finite set of non-negative even a path 𝑣1 𝑣2 β‹― 𝑣𝑛 containing no chord, i.e. any edge in integers and 𝔒 is a set of positive odd integers, the as- 𝐸(𝐺) is 𝑣𝑖 𝑣𝑖+1 ∈ 𝐸(𝐺) for some 1 ≀ 𝑖 < 𝑛. A 𝑃𝑛 path-graph sociated odd–even oriented digraph 𝐺 βƒ–βƒ— has vertex-set 𝔄 with a path 𝑣1 𝑣2 β‹― 𝑣𝑛 containing no chord is a bipartite and edge-set with π‘Žπ‘ ∈ 𝐸(𝐺) βƒ–βƒ— when both 1 (π‘Ž + 𝑏) and graph with (uniquely determined) color sets {𝑣1 , 𝑣3 , …} 2 1 2 (𝑏 βˆ’ π‘Ž) belong to 𝔒. This oriented bipartite graph has color classes π‘ˆ = {π‘Ž ∢ π‘Ž ≑ 0 (mod 4), π‘Ž ∈ 𝔄} and of π‘₯ is a vertex-colored digraph with color set 𝑆. π‘Š = {π‘Ž ∢ π‘Ž ≑ 2 (mod 4), π‘Ž ∈ 𝔄}. An oriented bipartite A truncation map 𝑒𝑇 ∢ 𝐿 Γ— 𝑆 β†’ 𝑇 assigns to every leaf digraph is a bitournament if for any two vertices 𝑒, 𝑣 ∈ 𝑉 π‘₯ ∈ 𝐿 and color 𝜎 ∈ 𝑆 a vertex of T such that 𝑒𝑇 (π‘₯, 𝑠) lies with different colors, either 𝑒𝑣 ∈ 𝐸(𝐺), βƒ–βƒ— or 𝑒𝑣 ∈ 𝐸(𝐺). βƒ–βƒ— A along the unique path from πœŒπ‘‡ to π‘₯ and that 𝑒𝑇 (π‘₯, 𝜎(π‘₯)) = bi-transitive bitournament is an odd-even digraph; see π‘₯. A leaf 𝑦 ∈ 𝐿 with color 𝜎(𝑦) is a quasi-best match for [4, Proposition 3.9]. π‘₯ ∈ 𝐿 (with respect to (𝑇 , 𝜎) and 𝑒𝑇 ) if both conditions (i) In addition, for four vertices π‘₯1 , π‘₯2 , π‘₯3 , 𝑦 of 𝐺, βƒ–βƒ— we say and (ii) are satisfied: (i) 𝑦 is a best match of π‘₯ in (𝑇 , 𝜎), (ii) that [π‘₯1 , π‘₯2 , π‘₯3 , 𝑦] is an (N1)-configuration if π‘₯1 π‘₯2 , π‘₯2 π‘₯3 , π‘™π‘π‘Žπ‘‡ (π‘₯, 𝑦) βͺ― 𝑒𝑇 (π‘₯, 𝜎(𝑦)). The digraph π‘žπ΅π‘€πΊ(𝑇 , 𝜎, 𝑒𝑇 ) is 𝑦π‘₯3 ∈ 𝐸(𝐺) βƒ–βƒ— but either π‘₯1 𝑦 ∈ 𝐸(𝐺) βƒ–βƒ— or 𝑦π‘₯1 ∈ 𝐸(𝐺); βƒ–βƒ— in other the vertex-colored digraph π‘žπ΅π‘€πΊ(𝑇 , 𝜎, 𝑒𝑇 ) on the vertex words when condition (N1) holds for 𝑒 = π‘₯1 , 𝑑 = π‘₯2 , 𝑀 = set 𝐿 whose edges are defined by the quasi-best matches. π‘₯3 , 𝑣 = 𝑦 and therefore π‘₯1 and 𝑦 are not independent. A vertex-colored digraph (𝐺, βƒ–βƒ— 𝜎) with vertex set 𝐿 is a A 2-qBMG is degenerate if it has an isolated vertex. We |𝑆|-colored quasi-best match graph (|S|-qBMG) if there is a stress that a non-degenerate 2-qBMG may be trivial, as leaf-colored tree (𝑇 , 𝜎) together with a truncation map 𝑒𝑇 it may be the union of pairwise disjoint (possible sym- on (𝑇 , 𝜎) such that (𝐺,βƒ–βƒ— 𝜎) = π‘žπ΅π‘€πΊ(𝑇 , 𝜎, 𝑒𝑇 ). For general metric) edges. If this is the case, then (N1), (N2), and (N3) results on quasi-best match graphs, the reader is referred trivially hold in the sense that none of the conditions re- to [1]. quired in (N1), (N2), and (N3) is satisfied. Also, a directed graph is said to be 𝑃𝑛 -free or 𝐢𝑛 -free if its undirected underlying graph is 𝑃𝑛 -free or 𝐢𝑛 -free, respectively. 3. Forbidden induced path graphs Let 𝐺 βƒ–βƒ—4 denote a bipartite digraph on four vertices of underlying undirected where 𝑉 (𝐺 βƒ–βƒ—4 ) = {π‘₯1 , π‘₯2 , 𝑦1 , 𝑦2 } and the color classes are 2-qBMGs {π‘₯1 , π‘₯2 } and {𝑦1 , 𝑦2 }. Then 𝐺 βƒ–βƒ—4 is of type (𝐹1 ) with required βƒ–βƒ— edges if 𝐸(𝐺4 ) = {π‘₯1 𝑦1 , 𝑦2 π‘₯2 , 𝑦1 π‘₯2 }. whereas 𝐺 βƒ–βƒ—4 is of type The main result in the paper which establishes a new βƒ–βƒ— (𝐹2 ) with required edges if 𝐸(𝐺4 ) = {π‘₯1 𝑦1 , 𝑦1 π‘₯2 , π‘₯2 𝑦2 }. The property of 2-qBMGs is given in the following theorem. undirected underlying graph 𝐺4 of a 𝐺 βƒ–βƒ—4 of type either Theorem 3.1. The underlying undirected graph of a 2- (𝐹1 ) or (𝐹2 ) is a path of length 4. qBMG is 𝑃6 -free. Let 𝐺 βƒ–βƒ—5 denote a bipartite graph on five vertices where 𝑉5 (𝐺 βƒ–βƒ—5 ) = {π‘₯1 , π‘₯2 , 𝑦1 , 𝑦2 , 𝑦3 } and the color classes are Proof. Let 𝐺 βƒ–βƒ— denote a 2-qBMG with at least six ver- {π‘₯1 , π‘₯2 } and {𝑦1 , 𝑦2 , 𝑦3 }. Then 𝐺 βƒ–βƒ—5 is of type (𝐹3 ) if with tices. Assume on the contrary that its underlying undi- required edges 𝐸(𝐺 βƒ–βƒ—5 ) = {π‘₯1 𝑦1 , π‘₯2 𝑦2 , π‘₯1 𝑦3 , π‘₯2 𝑦3 }. The undi- rected graph 𝐺 has an induced subgraph 𝐺6 on six ver- βƒ–βƒ—5 of type (𝐹3 ) is a path tices 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 such that 𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 𝑣6 is a 𝑃6 path- rected underlying graph 𝐺5 of 𝐺 graph: Then 𝐺6 contains no chord other than 𝑣𝑖 𝑣𝑖+1 for of length 5. βƒ–βƒ—1 and 𝐺 βƒ–βƒ—2 be two directed graphs on the same ver- 𝑖 = 1, … , 5. Four cases arise according to the possible Let 𝐺 βƒ–βƒ— βƒ–βƒ—1 β‰… 𝐺 βƒ–βƒ—2 , that is, 𝐺⃖⃗1 and 𝐺⃖⃗2 are isomorphic, patterns of the neighborhood of 𝑣2 in 𝐺. tex set 𝑉. Then 𝐺 βƒ–βƒ— βƒ–βƒ— otherwise (i): 𝑣1 𝑣2 , 𝑣3 𝑣2 ∈ 𝐸(𝐺). Then 𝑣3 𝑣4 ∈ 𝐸(𝐺), if there exists a edge-preserving permutation πœ‘ on 𝑉, i.e. [𝑣4 , 𝑣3 , 𝑣2 , 𝑣1 ] is an (N1)-quadruple. If 𝑣4 𝑣5 ∈ 𝐸(𝐺) βƒ–βƒ— then 𝑣1 𝑣2 ∈ 𝐸(𝐺 βƒ–βƒ—1 ) if and only if πœ‘(𝑣1 )πœ‘(𝑣2 ) ∈ 𝐸(𝐺 βƒ–βƒ—2 ). 𝑣6 𝑣5 ∈ 𝐸(𝐺), βƒ–βƒ— otherwise 𝑣3 𝑣4 𝑣5 𝑣6 violates (N2). On the A tree 𝑇 is phylogenetic if every node is either a leaf other hand, 𝑣4 𝑣5 , 𝑣6 𝑣5 ∈ 𝐸(𝐺) βƒ–βƒ— violates (N1) as [𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 ] or has at least two children. 𝑇 is a rooted tree if one of the nodes is chosen as root denoted by πœŒπ‘‡ . In a rooted is an (N1)-configuration. Hence 𝑣5 𝑣4 ∈ 𝐸(𝐺). βƒ–βƒ— If 𝑣6 𝑣5 ∈ tree, its root is typically drawn as the top node, and 𝐸(𝐺)βƒ–βƒ— then [𝑣6 , 𝑣5 , 𝑣4 , 𝑣3 ] is an (N1)-configuration. We the edges are directed from the parent nodes to their are left with the case 𝑣1 𝑣2 , 𝑣2 𝑣3 , 𝑣3 𝑣4 , 𝑣5 𝑣4 , 𝑣5 𝑣6 ∈ 𝐸(𝐺), βƒ–βƒ— as child nodes. In this contribution, all trees are rooted shown in Figure 1. and phylogenetic. Let (𝑇 , 𝜎) be a leaf-colored tree with In this case, (N3) does not hold for 𝑣3 and 𝑣5 since 𝑣4 ∈ leaf set 𝐿, set of colors 𝑆, leaf-coloring surjective map 𝑁 + (𝑣3 ) ∩ 𝑁 + (𝑣5 ) whereas 𝑣6 ∈ 𝑁 + (𝑣5 ) ⧡ 𝑁 + (𝑣3 ) and 𝑣2 ∈ 𝜎 ∢ 𝐿 β†’ 𝑆, and rooted at πœŒπ‘‡ . For any two leaves π‘₯, 𝑦 ∈ 𝑉, 𝑁 + (𝑣3 ) ⧡ 𝑁 + (𝑣5 ). π‘™π‘π‘Ž(π‘₯, 𝑦) denotes the last common ancestry between π‘₯ (ii): 𝑣1 𝑣2 , 𝑣2 𝑣3 ∈ 𝐸(𝐺). βƒ–βƒ— Then 𝑣4 𝑣3 ∈ 𝐸(𝐺), βƒ–βƒ— otherwise and 𝑦 on 𝑇. 𝑇 is phylogentic if all nodes have at least two 𝑣1 𝑣2 𝑣3 𝑣4 violates (N2). On the other hand, 𝑣4 𝑣3 ∈ 𝐸(𝐺) βƒ–βƒ— children except the leaves. A leaf 𝑦 ∈ 𝐿 is a best match yields that [𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 ] is an (N1)-configuration, a con- of the leaf π‘₯ ∈ 𝐿 if 𝜎(π‘₯) β‰  𝜎(𝑦) and π‘™π‘π‘Ž(π‘₯, 𝑦) βͺ― π‘™π‘π‘Ž(π‘₯, 𝑧), tradiction. i.e. π‘™π‘π‘Ž(π‘₯, 𝑧) is an ancestor of π‘™π‘π‘Ž(π‘₯, 𝑦), holds for all leaves (iii): 𝑣2 𝑣1 , 𝑣2 𝑣3 ∈ 𝐸(𝐺). βƒ–βƒ— Suppose 𝑣4 𝑣3 ∈ 𝐸(𝐺). βƒ–βƒ— Then (N3) 𝑧 of color 𝜎(𝑦) = 𝜎(𝑧). The BMG (best match graph) yields 𝑣5 𝑣4 ∈ 𝐸(𝐺) βƒ–βƒ— since 𝑣3 ∈ 𝑁 + (𝑣2 ) ∩ 𝑁 + (𝑣4 ) and 𝑣1 ∈ explained by (𝑇 , 𝜎) is the directed graph whose vertices βƒ–βƒ— then 𝑁 + (𝑣2 ) ⧡ 𝑁 + (𝑣4 ). On the other hand, if 𝑣5 𝑣4 ∈ 𝐸(𝐺) are the leaves of 𝑇 where π‘₯𝑦 ∈ 𝐸(𝐺) βƒ–βƒ— if 𝑦 is a best match v2 v4 v6 (i): 𝑣1 𝑣2 , 𝑣3 𝑣2 ∈ 𝐸(𝐺).βƒ–βƒ— The arguments in proof of The- orem 3.1 show that 𝑣4 𝑣3 βˆ‰ 𝐸(𝐺), βƒ–βƒ— and hence 𝑣3 𝑣4 ∈ 𝐸(𝐺). βƒ–βƒ— Moreover either 𝑣4 𝑣5 ∈ 𝐸(𝐺) βƒ–βƒ— or 𝑣5 𝑣4 ∈ 𝐸(𝐺), βƒ–βƒ— and the (π‘Ž) (𝑏) arising digraphs are 𝑃⃖⃗5 and 𝑃⃖⃗5 , respectively. Adding (π‘Ž) (𝑏) edges with consecutive endpoints to 𝐸(𝑃⃖⃗5 ) or 𝐸(𝑃⃖⃗5 ) provide more non-isomorphic 2-qBMGs: If we add 𝑣2 𝑣1 creating a symmetric edge arises, we obtain two more (π‘Ž1) (𝑏1) non-isomorphic digraphs, named 𝑃⃖⃗5 and 𝑃⃖⃗5 , respec- v1 v3 v5 (π‘Ž) (𝑏) tively. Adding 𝑣5 𝑣4 to 𝐸(𝑃⃖⃗5 ) or 𝑣4 𝑣5 to 𝐸(𝑃⃖⃗5 ), the same (𝑏1) βƒ–βƒ— up to possible symmetric Figure 1: Case (i): all edges of 𝐺 2-qBMG arises. Actually, it is isomorphic to 𝑃⃖⃗5 by the edges. map πœ‡ fixing 𝑣3 and swapping 𝑣2 with 𝑣4 , and 𝑣1 with 𝑣5 . (π‘Ž1) (𝑏1) (π‘Žπ‘) If we add 𝑣5 𝑣4 to 𝑃⃖⃗5 , or 𝑣4 𝑣5 to 𝑃⃖⃗5 , we obtain 𝑃⃖⃗5 . On the other hand, the above method does not work with [𝑣5 , 𝑣4 , 𝑣3 , 𝑣2 ] is an (N1)-configuration, a contradiction. 𝑣2 𝑣3 or 𝑣4 𝑣3 , since the arising digraph would not satisfy Hence 𝑣3 𝑣4 ∈ 𝐸(𝐺). βƒ–βƒ— If 𝑣4 𝑣5 ∈ 𝐸(𝐺) βƒ–βƒ— then [𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 ] (N2). is an (N1)-configuration, a contradiction. On the other (ii): 𝑣2 𝑣1 , 𝑣3 𝑣2 ∈ 𝐸(𝐺).βƒ–βƒ— The arguments in the proof of hand, if 𝑣5 𝑣4 ∈ 𝐸(𝐺) βƒ–βƒ— then 𝑣2 𝑣3 𝑣4 𝑣5 with 𝑣2 𝑣5 βˆ‰ 𝐸(𝐺) βƒ–βƒ— which Theorem 3.1 can also be used to show that 𝑣4 𝑣3 βˆ‰ 𝐸(𝐺), βƒ–βƒ— contradicts (N2). βƒ–βƒ— whence 𝑣3 𝑣4 ∈ 𝐸(𝐺) follows. Therefore, either 𝑣4 𝑣5 ∈ (iv): 𝑣2 𝑣1 , 𝑣3 𝑣2 ∈ 𝐸(𝐺). βƒ–βƒ— Then 𝑣3 𝑣4 ∈ 𝐸(𝐺), βƒ–βƒ— otherwise 𝐸(𝐺)βƒ–βƒ— or 𝑣5 𝑣4 ∈ 𝐸(𝐺). βƒ–βƒ— In the latter case, the digraph is βƒ–βƒ— (π‘Ž) 𝑣4 𝑣3 𝑣2 𝑣1 together with 𝑣4 𝑣1 βˆ‰ 𝐸(𝐺) violate (N2). Sup- isomorphic to 𝑃⃖⃗5 by the above map πœ‡. In the former pose that 𝑣5 𝑣4 ∈ 𝐸(𝐺). βƒ–βƒ— Then (N3) yields 𝑣6 𝑣5 ∈ 𝐸(𝐺), βƒ–βƒ— (𝑐) case, 𝑃⃖⃗5 is obtained, which is not isomorphic to any of + + + since 𝑣4 ∈ 𝑁 (𝑣3 ) ∩ 𝑁 (𝑣5 ) and 𝑣2 ∈ 𝑁 (𝑣3 ) ⧡ 𝑁 (𝑣5 ). + the 2-qBMGs already considered. Moreover, adding the However, 𝑣6 𝑣5 ∈ 𝐸(𝐺) βƒ–βƒ— contradicts (N1), as it yields that (𝑐) (π‘Ž1) edge 𝑣1 𝑣2 to 𝐸(𝑃⃖⃗5 ) gives 𝑃⃖⃗5 . Therefore, no further [𝑣6 , 𝑣5 , 𝑣4 , 𝑣3 ] is an (N1)-configuration. Therefore we have non-isomorphic 2-qBMGs arise since adding either 𝑣2 𝑣3 𝑣4 𝑣5 ∈ 𝐸(𝐺). βƒ–βƒ— If 𝑣6 𝑣5 ∈ 𝐸(𝐺) βƒ–βƒ— then [𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 ] is an (N1)- or 𝑣4 𝑣3 would violate (N2). configuration, a contradiction. On the other hand, if βƒ–βƒ— 𝑣3 𝑣4 𝑣5 𝑣6 with 𝑣3 𝑣6 βˆ‰ 𝐸(𝐺) βƒ–βƒ— violates (N2). (π‘Žπ‘) 𝑣5 𝑣6 ∈ 𝐸(𝐺), Remark 3.3. In Theorem 3.2, 𝑃⃖⃗5 is a 2-BMG explained by the phylogenetic tree (𝑇 , πœŽπ‘ ) in Figure 2, where πœŽπ‘ is Theorem 3.1 implies that the underlying undirected the leaf-coloring defined according to the parity of la- graph of any 2-qBMG is π‘ƒπ‘˜ free for π‘˜ β‰₯ 6, and also poses bels of the leaves. Moreover, the other five 2-qBMGs in the problem of π‘ƒπ‘˜ -freeness for 3 ≀ π‘˜ ≀ 5. Theorem 3.2 are explained by (𝑇 , πœŽπ‘ , 𝜏 ) where 𝜏 is an ap- Theorem 3.2. There exist 2-qBMGs on five vertices which propriate sink-truncation map depending on the digraph. are not 𝑃5 -free. More precisely, there are exactly six non- isomorphic 2-qBMGs on five vertices {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 } whose underlying undirected graph is a 𝑃5 path-graph with edge- sets are: (π‘Ž) 𝐸(𝑃⃖⃗5 ) = {𝑣1 𝑣2 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣4 𝑣5 }, (𝑏) 𝐸(𝑃⃖⃗5 ) = {𝑣1 𝑣2 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣5 𝑣4 }, (𝑐) v3 𝐸(𝑃⃖⃗5 ) = {𝑣2 𝑣1 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣4 𝑣5 }, (π‘Ž1) 𝐸(𝑃⃖⃗5 ) = {𝑣1 𝑣2 , 𝑣2 𝑣1 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣4 𝑣5 }, (𝑏1) 𝐸(𝑃⃖⃗5 ) = {𝑣1 𝑣2 , 𝑣2 𝑣1 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣5 𝑣4 }, (π‘Žπ‘) 𝐸(𝑃⃖⃗5 ) = {𝑣1 𝑣2 , 𝑣2 𝑣1 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣4 𝑣5 , 𝑣5 𝑣4 }. v1 v2 v4 v5 Proof. Let 𝐺⃖⃗ be a 2-qBMG on five vertices such that its Figure 2: Tree topology explaining all digraphs in Theorem 3.2. underlying undirected graph 𝐺 has five pairwise distinct Leaves 𝑣1 , 𝑣3 , 𝑣5 have the same color opposite to the color of leaves 𝑣2 , 𝑣4 . vertices, say 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 where 𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 is a path con- taining no chord other than 𝑣𝑖 𝑣𝑖+1 for 𝑖 = 1, … , 4. The arguments in the proof of Theorem 3.1 show that no βƒ–βƒ— 2-qBMG satisfies either 𝑣1 𝑣2 , 𝑣2 𝑣3 ∈ 𝐸(𝐺) βƒ–βƒ— or 𝑣2 𝑣1 , 𝑣2 𝑣3 ∈11 Example 3.4. The 2-qBMG 𝐺 on 7 vertices {𝑣1 , 𝑣2 , … , 𝑣7 } and edge-set βƒ–βƒ— Therefore, two cases arise only according to the 𝐸(𝐺). possible patterns of the neighborhood of 𝑣2 . βƒ–βƒ— = {𝑣5 𝑣4 , 𝑣2 𝑣1 , 𝑣3 𝑣4 , 𝑣3 𝑣2 , 𝑣4 𝑣7 , 𝑣1 𝑣6 , 𝑣3 𝑣6 , 𝑣6 𝑣1 , 𝑣7 𝑣4 } 𝐸(𝐺) is an example of a larger 2-qBMG whose induced sub- hand, 2-qBMGs with paths and cycles of length β„“ < 5 (π‘Ž1) βƒ–βƒ— on 4 vertices graph on {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 } coincides with 𝑃⃖⃗5 . exist. For β„“ = 4, consider the digraph 𝐺 {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 } and edge-set 𝐸(𝐺) βƒ–βƒ— = {𝑣2 𝑣1 , 𝑣2 𝑣3 , 𝑣3 𝑣4 }. The A case-by-case analysis similar but simpler to those in βƒ–βƒ— is a path of length 4, and 𝐺 βƒ–βƒ— is a underlying graph of 𝐺 the proof of Theorem 3.2 gives the following result. 2-qBMG; indeed it is explained by (𝑇 , πœŽπ‘ , 𝜏 ), where 𝑇 is Theorem 3.5. There are exactly four non-isomorphic 2- represented in Figure 3(a), πœŽπ‘ is the leaf-coloring map qBMGs on four vertices {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 } whose underlying defined by the parity of the leaf labels and 𝜏 is the sink- undirected graph is a 𝑃4 path-graph: truncation maps of 𝐺. For 𝑙 = 3, consider the digraph 𝐺 βƒ–βƒ— βƒ–βƒ—(1) 𝐸(𝑃4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣2 𝑣3 }, on 3 vertices {𝑣 , 𝑣 1 2 3, 𝑣 } and edge-set βƒ–βƒ— 𝐺 = {𝑣 𝑣 , 2 1 2 3𝑣 𝑣 } is a (2) 2-qBMG explained by (𝑇 , 𝜎 , 𝜏 ), where 𝑇 is in Figure 3(b). 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣3 𝑣4 }, 𝑝 βƒ–βƒ—(3) The underlying graph of βƒ–βƒ— is a path of length 3. 𝐺 𝐸(𝑃4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣2 𝑣1 , 𝑣2 𝑣3 }, (4) 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣2 𝑣1 , 𝑣4 𝑣1 , 𝑣4 𝑣3 }. In Theorem 3.5, all the non-isomorphic 2-qBMGs on four vertices contain a sink. Therefore, the undirected (a) (b) underlying graph of a 2BMG is 𝑃4 -free since 2BMGs are sink-free 2-qBMG. Corollary 3.6. The underlying undirected graph of a 2BMG is a cograph. v3 v4 v2 v1 v1 v2 v3 The 𝑃3 -freeness problem is solved in the following proposition. Figure 3: (a) Tree topology explaining a 2-qBMG with an Proposition 3.7. Every bipartite digraph on three vertices induced 𝑃4 . (b) Tree topology explaining a 2-qBMG with an {𝑣1 , 𝑣2 , 𝑣3 } is a 2-qBMG. induced 𝑃3 . Proof. It is straightforward to check that both (N1) and (N2) hold trivially for every bipartite digraph 𝐺 βƒ–βƒ— on three The arguments used in the proof of Theorem 3.2 can vertices. For (N3), it also holds trivially when |𝐸(𝐺)|βƒ–βƒ— = 1. be adapted to prove the following theorem. βƒ–βƒ— On the other hand, assign a vertex-coloring on 𝑉 (𝐺) such that 𝑣1 and 𝑣3 have the same color. The only case when Theorem 3.11. There are exactly 10 non-isomorphic 2- two vertices have at least one common out-neighbor is qBMGs on four vertices {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 } whose underlying undirected graph is a 𝐢4 . They are the following ten di- when 𝑁 + (𝑣1 ) = 𝑁 + (𝑣3 ) = {𝑣2 }. Hence, (N3) holds also in the case when |𝐸(𝐺)|βƒ–βƒ— > 1. graphs: (1) 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣2 𝑣1 , 𝑣2 𝑣3 , 𝑣3 𝑣4 , 𝑣4 𝑣3 }, A straightforward consequence of Proposition 3.7 is a 𝐸(𝑃⃖⃗(2) ) = {𝑣 𝑣 , 𝑣 𝑣 , 𝑣 𝑣 , 𝑣 𝑣 , 𝑣 𝑣 , 𝑣 𝑣 }, 4 1 2 1 4 2 3 3 2 3 4 4 3 characterization of the 2-qBMGs on three vertices whose (3) 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣3 𝑣2 , 𝑣3 𝑣4 }, underlying undirected graph is a 𝑃3 path-graph. (4) 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣3 𝑣2 , 𝑣4 𝑣3 }, Corollary 3.8. The non-isomorphic 2-qBMGs on three 𝐸(𝑃⃖⃗(5) ) = {𝑣 𝑣 , 𝑣 𝑣 , 𝑣 𝑣 , 𝑣 𝑣 , 𝑣 𝑣 }, 4 1 2 2 1 3 2 3 4 4 1 vertices whose underlying undirected graph is a 𝑃3 path- (6) 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣3 𝑣2 , 𝑣4 𝑣1 , 𝑣4 𝑣3 }, graph are all bipartite digraphs with at least two edges (7) except for a symmetric edge. 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣2 𝑣3 , 𝑣4 𝑣3 }, (8) 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣4 𝑣3 }, The same setup and arguments from the proof of The- βƒ–βƒ—(9) orem 3.1 can be used to deal with induced 6-cycles in 𝐸(𝑃4(10)) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣2 𝑣1 , 𝑣2 𝑣3 , 𝑣3 𝑣2 , 𝑣3 𝑣4 }, 2-qBMGs since the proof of Theorem 3.1 involves neither 𝐸(𝑃⃖⃗4 ) = {𝑣1 𝑣2 , 𝑣1 𝑣4 , 𝑣3 𝑣2 , 𝑣3 𝑣4 , 𝑣2 𝑣1 , 𝑣2 𝑣3 , 𝑣4 𝑣1 , 𝑣4 𝑣3 }. 13 𝑣1 𝑣6 nor 𝑣6 𝑣1 . Therefore, the following result holds. Theorem 3.9. The underlying undirected graph of any 2-qBMG is 𝐢6 -free. 4. Dominating sets in 2-qBMGs Remark 3.10. 2-qBMGs are bipartite digraphs; there- As pointed out in the introduction, Theorem 3.1 and fore, they cannot induce cycles of an odd length. In Theorem 3.9, together with previous results, give new particular, they are 𝐢5 -free and 𝐢3 -free. On the other contributions to the current studies on the structure of 2-qBMGs. This section is focused on dominating biclique βƒ–βƒ— Ξ“ has a topological ordering. Therefore, the vertices of sets. βƒ–βƒ— Ξ“ can be labelled with {𝑣1 , 𝑣2 , … , 𝑣𝑛 } such that 𝑣𝑖 𝑣𝑗 ∈ 𝐸(βƒ–βƒ— Ξ“) Recall that a connected 2-qBMG is of type (A) if its implies 𝑖 < 𝑗 for 1 ≀ 𝑖, 𝑗 ≀ 𝑛. In particular, for 𝑣𝑖 , 𝑣𝑗 ∈ undirected underlying graph has a vertex decomposition 𝑉 (Ξ”) of different color, either 𝑣𝑖 𝑣𝑗 or 𝑣𝑗 𝑣𝑖 is an edge of βƒ–βƒ—Ξ”. into a biclique and a stable set. It may be observed that βƒ–βƒ— Therefore, (N1) trivially holds for Ξ” while (N2) follows such a biclique is necessarily a dominating set. from the transitivity of the ordering. To show (N3), take Example 4.1. The digraph on 10 vertices {𝑣1 , 𝑣2 , … , 𝑣10 } 𝑣𝑖 , 𝑣𝑗 ∈ 𝑉 (Ξ”) of the same color such that 𝑣𝑖 and 𝑣𝑗 have with edge-set a common out-neighbour 𝑀 ∈ βƒ–βƒ— Ξ”. Then 𝑀 is a common out-neighbour of 𝑣𝑖 and 𝑣𝑗 in 𝐺. βƒ–βƒ— From (N3) applied to βƒ–βƒ— = {𝑣1 𝑣5 , 𝑣1 𝑣6 , 𝑣1 𝑣7 , 𝑣1 𝑣8 , 𝑣5 𝑣2 , 𝑣6 𝑣2 , 𝑣2 𝑣7 , 𝑣2 𝑣8 , 𝑣5 𝑣3 , 𝑣6 𝑣3 , 𝐸(𝐺) βƒ–βƒ— all out-neighbours of 𝑣𝑖 in 𝐺 𝐺, βƒ–βƒ— are also out-neighbours 𝑣3 𝑣7 , 𝑣3 𝑣8 , 𝑣5 𝑣4 , 𝑣6 𝑣4 , 𝑣7 𝑣4 , 𝑣4 𝑣8 , 𝑣5 𝑣9 , 𝑣1 𝑣10 , 𝑣2 𝑣10 } of 𝑣𝑗 (or, vice versa). Now take any vertex 𝑣 such that βƒ–βƒ— βƒ–βƒ— βƒ–βƒ— is a 2-qBMG of type (A) whose underlying undirected 𝑣𝑖 𝑣 ∈ 𝐸(Ξ”). Then 𝑣𝑖 𝑣 ∈ 𝐸(𝐺), and hence 𝑣𝑗 𝑣 ∈ 𝐸(𝐺). Since graph 𝐺 has an induced dominating subgraph with vertex 𝑣𝑗 𝑣 is not a symmetric edge in 𝐺, this yields 𝑣𝑗 𝑣 ∈ 𝐸(βƒ–βƒ— βƒ–βƒ— Ξ“) set {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 , 𝑣7 , 𝑣8 } and stable set {𝑣9 , 𝑣10 }. whence 𝑣𝑗 𝑣 ∈ 𝐸(βƒ–βƒ—Ξ”) follows. Thus βƒ–βƒ— Ξ” is a 2-qBMG. Theorem 4.2. Every connected 2-qBMG has a vertex de- Theorem 4.4. Let 𝐺 βƒ–βƒ— be a connected 2-qBMG satisfying composition into connected 2-qBMGs of type (A). βƒ–βƒ— has an even-odd subgraph (𝔄, 𝔒) such that the (βˆ—). Then 𝐺 Proof. Let 𝐺 βƒ–βƒ— be a connected 2-qBMG not of type (A). Let underlying undirected subgraph of (𝔄, 𝔒) is a dominating 𝐺 be the underlying undirected graph of 𝐺, βƒ–βƒ— where π‘ˆ and biclique of 𝐺. π‘Š are its color classes. As mentioned in the introduction, Proof. Fix an orientation βƒ–βƒ— Ξ“ of 𝐺⃖⃗ by keeping the same from [15, Theorem 1], 𝐺 contains a dominating biclique vertex set but retaining exactly one edge from each sym- Ξ” with vertex set 𝑇 βˆͺ 𝑍 where 𝑇 βŠ† π‘ˆ and 𝑍 βŠ† π‘Š. Let metric edge. Let 𝐺 be the underlying undirected graph βƒ–βƒ— Ξ” be the directed subgraph of 𝐺 βƒ–βƒ— induced by Ξ”. Let 𝑆 be βƒ–βƒ— Then 𝐺 coincides with the underlying undirected of 𝐺. the subset of 𝑉 (𝐺) consisting of all vertices 𝑣 ∈ 𝑉 (𝐺) for graph of βƒ–βƒ— Ξ“. As mentioned in Introduction, from [15, The- which 𝑁 + (𝑣) βˆͺ 𝑁 βˆ’ (𝑣) is contained in 𝑇 βˆͺ 𝑍. Let βƒ–βƒ— Ξ£ be the βƒ–βƒ— on 𝑇 βˆͺ𝑍 βˆͺ𝑆. Since Ξ” is a dominating orem 1], 𝐺 contains a dominating biclique Ξ” with vertex induced subgraph of 𝐺 set 𝑇 βˆͺ 𝑍 where 𝑇 βŠ† π‘ˆ and 𝑍 βŠ† π‘Š where π‘ˆ and π‘Š are the set of 𝐺, βƒ–βƒ—Ξ£ is connected without isolated vertex and is a bipartion classes of 𝐺. Let βƒ–βƒ— Ξ” be the directed subgraph on connected 2-qBMG. The underlying undirected graph Ξ£ βƒ–βƒ— vertex-set 𝑇 βˆͺ 𝑍 where 𝑣𝑖 𝑗 ∈ 𝐸(Ξ”) if and only if 𝑣𝑖 𝑣𝑗 is an 𝑣 of βƒ–βƒ— Ξ£ is a 𝐾 βŠ• 𝑆 graph, where 𝐾 = 𝑇 βˆͺ 𝑍. βƒ–βƒ— βƒ–βƒ— Furthermore, let 𝐺 βƒ–βƒ—1 be the induced subgraph of 𝐺 βƒ–βƒ— on edge of Ξ“. It should be noticed that Ξ” may not be the in- βƒ–βƒ— 𝑉 (𝐺) ⧡ (𝑇 βˆͺ 𝑍 βˆͺ 𝑆). By construction, no vertex of 𝐺 βƒ–βƒ—1 duced subgraph of 𝐺 on the vertex-set 𝑇 βˆͺ 𝑍. This occurs indeed when 𝐺 βƒ–βƒ— contains a symmetric edge with both end- is isolated, although some vertex of 𝐺 may become a βƒ–βƒ— βƒ–βƒ— sink in 𝐺 βƒ–βƒ—1 , and non-equivalent vertices 𝐺 βƒ–βƒ— may become points in 𝑇 βˆͺ 𝑍. Nevertheless, Ξ” is bitournament. Since βƒ–βƒ— equivalent in 𝐺 βƒ–βƒ—1 . If 𝐺1 is not a connected 2-qBMG of type Ξ” is bitransitive, it is an even-odd digraph, as recalled in Section 2. (A), we can repeat the above construction to define a finite sequence Ξ£1 , 𝐺2 , Ξ£2 … , Ξ£π‘˜ such that βƒ–βƒ— Ξ£, βƒ–βƒ— Ξ£1 , βƒ–βƒ— Ξ£2 , … , βƒ–βƒ— Ξ£π‘˜ form a vertex partition of 𝐺 into connected 2-qBMGs of 5. Future directions βƒ–βƒ— type (A). If some of the members of the subsequence The 𝑃6 -and 𝐢6 -freeness in the undirected underlying 2- 𝐺1 , 𝐺2 , … , πΊπ‘˜βˆ’1 decomposition is not connected, say πΊπ‘š , qBMGs raises the problem of finding more such forbidden applying the above argument on each of the connected subgraphs on six (or eight) vertices. In this direction, the components of πΊπ‘š gives the claimed partition. domino graph on six vertices (i.e. the Cartesian product 𝑃2 Γ— 𝑃3 ) and its generalization on eight vertices, the long- Proposition 4.3. Let 𝐺 βƒ–βƒ— be a 2-qBMG satisfying at least domino or ladder graph, appearworth investigating. one of conditions (βˆ—) and (βˆ—βˆ—). Fix an orientation βƒ–βƒ— Ξ“ of 𝐺.βƒ–βƒ— Let In [20], bipartite 𝑃6 and 𝐢6 -free graphs are character- βƒ–βƒ— Ξ” be an induced subgraph of βƒ–βƒ— Ξ“ such that the underlying ized as those graphs where every connected subgraph is undirected graph Ξ” is a biclique of 𝐺. If 𝐺 βƒ–βƒ— has no symmetric of type 𝐾 βŠ• 𝑆. This gives rise to a linear time algorithm for recognizing if an undirected graph is 𝑃6 and 𝐢6 -free edges in βƒ–βƒ— Ξ” then βƒ–βƒ— Ξ” is a 2-qBMG. by tracing all 𝐾 βŠ• 𝑆 decompositions. It would be inter- Proof. Let 𝑛 be the number of the vertices of 𝐺 βƒ–βƒ— (and of βƒ–βƒ— Ξ“). esting to investigate whether a similar approach can be As pointed out in Section 2, if either (βˆ—) or (βˆ—βˆ—) holds then used to perform a linear time algorithm to recognize if a digraph is a 2-qBMG. The first step is to check whether [9] G. Manuela, P. F. Stadler, M. Hellmuth, Reciprocal the converse of [20, Theorem 2] holds. best match graphs, J. Math. Biology 80 (2020). The s-dim of a graph 𝐺 is the minimum number of [10] M. Hellmuth, M. Geiß, P. F. Stadler, Complexity bicliques needed to cover the edge-set of 𝐺. Computing of modification problems for reciprocal best match the s-dim (biclique cover problem) is NP-complete for graphs, Theoretical Computer Science 809 (2020). bipartite graphs [21]; however, this problem is linear for [11] G. BacsΓ³, Z. Tuza, Domination properties and in- some classes of graphs, such as bipartite domino-free duced subgraphs, Discr. Math. 111 (1993) 37–40. graphs [22]. Investigating the complexity of the biclique [12] G. BacsΓ³, D. Michalak, Z. Tuza, Dominating bipar- cover problem for the family of underlying undirected tite subgraphs in graphs, Discussiones Mathemati- graphs of 2-qBMGs is also an interesting topic for future cae Graph Theory 25 (2005) 85–94. investigation. [13] A. BrandstΓ€dt, T. Klembt, S. Mahfud, P6- For two disjoint subsets π‘Š and 𝑇 of vertices, π‘Š 2- and triangle-free graphs revisited: structure and dominates 𝑇 if every vertex of 𝑇 is adjacent to at least bounded clique-width, Discrete Mathematics & two vertices of π‘Š. A partition {𝑉1 , 𝑉2 , … , 𝑉𝑛 } of vertices Theoretical Computer Science 8 (2006). in 𝑉 (𝐺) into 𝑛 parts is a 2-transitive partition of size 𝑛 if 𝑉𝑖 [14] P. van’t Hof, D. Paulusma, A new characterization 2-dominates for all 1 ≀ 𝑖 < 𝑗 ≀ 𝑛. Finding a 2-transitivity of p6 -free graphs, Discr. Appl. Math. 158 (2010) partition of maximum order is NP-complete for bipartite 731–740. graphs [23]. Studying the complexity of this problem for [15] J. Liu, H. Zhou, Dominating subgraphs in graphs the family of underlying undirected graphs of 2-qBMGs with some forbidden structures, Discr. Math. 135 is also an interesting topic for future investigation. (1994) 163–168. [16] J. Liu, Y. Peng, C. Zhao, Characterization of p6 -free graphs, Discr. Appl. Math. 155 (2007) 1038–1043. References [17] R. Peeters, The maximum edge biclique problem is np-complete, Discrete Applied Mathematics 131 [1] A. Korchmaros, D. Schaller, M. Hellmuth, P. F. (2003) 651–654. Stadler, Quasi-best match graphs, Discr. Appl. Math. [18] E. Prisner, Bicliques in graphs I: bounds on their 331 (2023) 104–125. number, Combinatorica 20 (2000) 197–207. [2] J. A. RamΓ­rez-Rafael, A. Korchmaros, K. AviΓ±a- [19] J.-L. Fouquet, V. Giakoumakis, J.-M. Vanherpe, Bi- Padilla, A. LΓ³pez SΓ‘nchez, A. A. EspaΓ±a-Tinajero, partite graphs totally decomposable by canonical M. Hellmuth, P. F. Stadler, M. HernΓ‘ndez-Rosales, decomposition, International Journal of Founda- Revolutionh-tl: Reconstruction of evolution ary tions of Computer Science 10 (1999) 513–533. histories tool, in: RECOMB International Work- [20] R. Quaddoura, A. Al-Qerem, Bipartite (P6 ,C6 )-free shop on Comparative Genomics, Springer, 2024, pp. graphs: Recognition and optimization problems, 89–109. Symmetry 16 (2024) 447. [3] D. Schaller, M. Geiß, E. ChΓ‘vez, M. GonzΓ‘lez Laf- [21] M. Dawande, P. Keskinocak, J. M. Swaminathan, fitte, A. LΓ³pez SΓ‘nchez, B. M. Stadler, D. I. Valdivia, S. Tayur, The biclique cover problem for bipartite M. Hellmuth, M. HernΓ‘ndez Rosales, P. F. Stadler, graphs, SIAM Journal on Discrete Mathematics 15 Corrigendum to β€œbest match graphs”, J. Math. Biol- (2001) 255–271. ogy 82 (2021). [22] J. Amilhastre, M.-C. Vilarem, P. Janssen, Com- [4] A. Korchmaros, The structure of 2-colored best plexity of minimum biclique cover and minimum match graphs, Discr. Appl. Math. 304 (2021). biclique decomposition for bipartite domino-free [5] D. Schaller, M. Geiß, M. Hellmuth, P. F. Stadler, graphs, Discr. Appl. Math. 86 (1998) 125–144. Heuristic algorithms for best match graph editing, [23] S. Paul, K. Santra, Algorithmic study on Algorithms for Molecular Biology 16 (2021). 2-transitivity of graphs, arXiv preprint [6] D. Schaller, P. F. Stadler, M. Hellmuth, Complexity arXiv:2310.04036 (2023). of modification problems for best match graphs, Theoretical Computer Science 865 (2021). [7] D. Schaller, M. Geiß, P. F. Stadler, M. Hellmuth, Complete characterization of incorrect orthology assignments in best match graphs, J. Math. Biology 82 (2021). [8] M. Hellmuth, P. F. Stadler, The theory of gene family histories, in: Comparative Genomics: Methods and Protocols, Springer, 2024, pp. 1–32.