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. Phylogenetic combinatorics, quasi best match graphs, 6- and 6-free graphs, dominating set, vertex decomposition.
Quasi-best match graphs are directed vertex-colored acterization is known so far for the case of two colors [1]: A two-color quasi best match graph (2-qBMG) is a bipartite directed graph ⃖⃗ without loops and parallel edges which has the following three properties: (N1) if and are two independent vertices then there exist no vertices , such that , ,
are edges; (N2) bi-transitive, i.e., if , ,
are edges then is (N3) if and have common out-neighbor then either all out-neighbors of are also out-neighbors of or all out-neighbors of are also out-neighbors also an edge; of .
by three types of forbidden induced subgraphs, called of types ( 1), ( 2) and ( 3); see Section 2.
This investigation focuses on specific properties of such undirected graphs have been touched so far only marginally in the study of 2-qBMGs except in the very special case of reciprocal 2-BMGs; see [9, 10]. The main motivation for this study is the richness of the literature on undirected graphs. It is indeed much richer than on directed graphs, with plenty of fundamental works on forbidden configurations, decompositions, and vertexcolorings, as well as on algorithms and valuations on computational complexity. The aim is to exploit some of these deeper results on undirected graphs to gain new insights into 2-qBMGs. It may happen, however, that going back to a digraph ⃖⃗ from its underlying undirected graph , a deep result on only has a very limited, or even trivial impact on ⃖⃗. Thus, the structural relationship between ⃖⃗ and is far to be immediate. For instance, [6, Theorem 3.4] does not yield an analog characterization CEUR
ceur-ws.org
A 2-qBMG is a two-colored best match graph (2-BMG) if it is sink-free, i.e., no vertex has empty out-neighborhood, and it is a reciprocal two-best match graph (reciprocal 2- in terms of forbidden induced subgraphs of the underBMG) 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].
2-BMGs, 2-qBMGs, and more generally best match graphs have been the subjects of intensive studies, also the underlying undirected graph of a digraph of type ( ), 1 ≤ ≤ 3 with only required edges is either a path of 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 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. nEvelop-O LGOBE 0000-0002-7334-669X (A. Korchmaros) CEUR htp:/ceur-ws.org ISN1613-073 © 2022 Copyright for this paper by its authors. Use permitted under Creative
CEUR
Workshop Proceedings (CEUR-WS.org)
The main results in this direction are Theorem 3.1 and Theorem 3.9, which state that the underlying undirected graph of every 2-qBMG is 6-free and 6-free, that is, both 6 and 6 are forbidden induced subgraphs. This result is sharp as the underlying undirected graph of a 2qBMG may have an induced path 5 (and hence induced 4 as well); see Theorem 3.2. Therefore, the underlying undirected graphs of a type ( ) digraph, 1 ≤ ≤ 3 , are not forbidden subgraphs for the underlying undirected graph of 2-qBMGs.
In their seminal paper [11] appeared in 1993, Bacsó and Tuza pointed out the strong relationship between and { 2, 4, …}. An undirected graph is -free if it has no induced subgraph isomorphic to a path-graph. A cograph is a 4-free graph.
A cycle of an undirected graph is a sequence 1 2 ⋯ 1 of pairwise distinct vertices of such that +1 ∈ () for = 1, … , − 1 , and 1 ∈ () . A Paulusma [14] where the authors also provide an algo- to an cycle-graph. -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 in several papers, especially in [12, 13, 14, 15, 16]. In par- () ticular, for any bipartite graph , Liu and Zhou proved that is both 6-free and 6-free if and only if every connected induced subgraph of has a dominating biclique; see [15, Theorem 1]. An independent constructive proof cycle 1 2 ⋯ 1 containing no chord, i.e. any edge in is either +1 ∈ ()
for some 1 ≤ ≤ − 1 , or 1. For even, a cycle-graph with a cycle 1 2 ⋯ 1 containing no chord is a bipartite graph with (uniquely determined) color classes { 1, 3, …} and { 2, 4, …}. Bipartite 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 rithm that finds such a dominating biclique of a connected 6-free graph in polynomial time. For a discussion on the computational complexity of the problem of finding (not necessarily dominating) bicliques in undirected bipartite A set ⊆ ()
is a dominating set of an undirected graph if, for any vertex ∈ () ⧵
, there is a vertex ∈ such that ∈ ()
. We also say that dominates . 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 . of the sizes of their color classes , cliques of 6-free undirected bipartite graphs in terms Theorem 3.3] where it is shown that such number does not exceed | | 2| | 2
.
Recognition and optimization problems for both 6 and 6-free bipartite undirected graphs and certain de- set ( )⃖⃗ , in particular for 2-qBMGs, notation and termicompositions 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
is given in [18, degenerate, i.e. if it has an isolated vertex, or there is a partition of ()
into two sets: a biclique set and a stable set ; see [19, 20].
For directed graphs ⃖⃗ with vertex-set ( )⃖⃗ and edgeit is shown that the class of both 6 and 6-free bipartite graphs can be recognized in linear time. Also, eficient solutions for two NP-hard problems are presented in this class of graphs: the maximum balanced biclique problem and the maximum independent set problem. For more details, see the recent paper [20].
A contribution to the study of the vertex decomposition problem for 2-qBMGs in smaller connected 2-qBMGs of type (A) is given in Theorem 4.2, where a connected 2-qBMG is of type (A) if its underlying undirected graph is a ⊕
graph, that is, it has a vertex decomposition into a (dominating) biclique and a stable set , that is, any two vertices in are independent.
The notation and terminology for undirected graphs are standard. Let be an undirected graph with vertex-set () and edge-set ()
. In particular, a path of an undirected graph is a sequence 1 2 ⋯ of pairwise distinct vertices of such that +1
∈ () () A path-graph is an undirected graph on vertices with a path 1 2 ⋯ containing no chord, i.e. any edge in is +1 ∈ ()
for some 1 ≤ < . A path-graph with a path 1 2 ⋯ containing no chord is a bipartite graph with (uniquely determined) color sets { 1, 3, …} when −( ) = ∅ . A digraph ⃖⃗is oriented if ∈ ( in ⃖⃗, and is a sink when +( ) = ∅ , and is a source
)⃖⃗ implies ∉ ( )⃖⃗ for any , ∈ (
)⃖⃗ . An oriented digraph has a topological vertex ordering if its vertices can be labeled with 1, 2, … such that for any ∈ ( )⃖⃗ we have < . A suficient condition for an oriented digraph to have a topological ordering is to be acyclic, that is, there is no directed cycle in the digraph. An orientation of a digraph ⃖⃗ is a digraph obtained from ⃖⃗ by keeping the same vertex set but retaining exactly one edge from each symmetric edge. From [4, Lemma 2.2] and [4, Theorem 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 ⃖⃗
have a common endpoint; (∗∗) no two (or more than two) vertices of ⃖⃗are equivalent, i.e. no two vertices have the same in- and out-neighbors. pair (, )
where is a finite set of non-negative even integers and is a set of positive odd integers, the associated odd–even oriented digraph ⃖⃗ has vertex-set and edge-set with ∈ ( )⃖⃗ when both 1 ( + )
and 2 ( − )
belong to . This oriented bipartite graph has for = 1, … , −1 . Acyclic-oriented digraphs are odd–even graphs. For a 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 diferent 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 3. Forbidden induced path graphs underlying graph is -free or -free, respectively.
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 undirequired edges ( ⃖⃗5) = { 1 1, 2 2, 1 3, 2 3}. The undi- rected graph has an induced subgraph 6 on six verrected underlying graph 5 of ⃖⃗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 pathof length 5. graph: Then 6 contains no chord other than +1 for = 1, … , 5 . Four cases arise according to the possible Let ⃖⃗1 and ⃖⃗2 be two directed graphs on the same verpatterns of the neighborhood of 2 in ⃖⃗. tex set . Then ⃖⃗1 ≅ ⃖⃗2, that is, ⃖⃗1 and ⃖⃗2 are isomorphic, if there exists a edge-preserving permutation on , i.e. (i): 1 2, 3 2 ∈ ( )⃖⃗ . Then 3 4 ∈ ( )⃖⃗, otherwise 1 2 ∈ ( ⃖⃗1) if and only if ( 1)( 2) ∈ ( ⃖⃗2). [ 4, 3, 2, 1] is an (N1)-quadruple. If 4 5 ∈ ( )⃖⃗ then
A tree is phylogenetic if every node is either a leaf 6 5 ∈ ( )⃖⃗ , otherwise 3 4 5 6 violates (N2). On the or has at least two children. is a rooted tree if one of other hand, 4 5, 6 5 ∈ ( )⃖⃗ violates (N1) as [ 3, 4, 5, 6] 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 conof 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 +( 2) ⧵ +( 4). On the other hand, if 5 4 ∈ ( )⃖⃗ then are the leaves of where ∈ ( )⃖⃗ if is a best match
(i): 1 2, 3 2 ∈ ( )⃖⃗ . The arguments in proof of Theorem 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 non-isomorphic digraphs, named ⃖⃗5(1) and ⃖⃗5(1) , respectively. Adding 5 4 to ( ⃖⃗5() ) or 4 5 to ( ⃖⃗5() ), the same
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 lagraph 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 appropriate sink-truncation map depending on the digraph.
Theorem 3.2. There exist 2-qBMGs on five vertices which are not 5-free. More precisely, there are exactly six nonisomorphic 2-qBMGs on five vertices { 1, 2, 3, 4, 5} whose underlying undirected graph is a 5 path-graph with edgesets are: ( ⃖⃗5() ) = { 1 2, 3 2, 3 4, 4 5}, ( ⃖⃗5() ) = { 1 2, 3 2, 3 4, 5 4}, ( ⃖⃗5() ) = { 2 1, 3 2, 3 4, 4 5}, ( ⃖⃗5(1) ) = { 1 2, 2 1, 3 2, 3 4, 4 5}, ( ⃖⃗5(1) ) = { 1 2, 2 1, 3 2, 3 4, 5 4}, ( ⃖⃗5() ) = { 1 2, 2 1, 3 2, 3 4, 4 5, 5 4}.
Proof. Let ⃖⃗be a 2-qBMG on five vertices such that its underlying undirected graph has five pairwise distinct vertices, say 1, 2, 3, 4, 5 where 1 2 3 4 5 is a path con- leaves 2, 4. taining no chord other than +1 for = 1, … , 4 . The arguments in the proof of Theorem 3.1 show that no Example 3.4. The 2-qBMG ⃖⃗on 7 vertices { 1, 2, … , 7} 2-qBMG satisfies either 1 2, 2 3 ∈ ( )⃖⃗ or 2 1, 2 3 ∈11 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} v3 v1 v2 v4
v5 ( ⃖⃗4(2)) = { 1 2, 1 4, 3 4}, ( ⃖⃗4(3)) = { 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 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. graph on { 1, 2, 3, 4, 5} coincides with ⃖⃗5(1) . is an example of a larger 2-qBMG whose induced sub- hand, 2-qBMGs with paths and cycles of length ℓ < 5 exist. For ℓ = 4, consider the digraph ⃖⃗ on 4 vertices { 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 underlying graph of ⃖⃗ is a path of length 4, and ⃖⃗ is a 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 sinkundirected graph is a 4 path-graph: truncation maps of . For = 3 , consider the digraph ⃖⃗ ( ⃖⃗4(1)) = { 1 2, 1 4, 2 3}, on 3 vertices { 1, 2, 3} and edge-set ⃖⃗= { 2 1, 2 3} is a 2-qBMG explained by ( , , ) , where is in Figure 3(b).
The underlying graph of ⃖⃗ is a path of length 3.
(a)
(b) v3 v4 v2 v1 v1 v2 v3
The 3-freeness problem is solved in the following proposition.
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 2two vertices have at least one common out-neighbor is qBMGs on four vertices { 1, 2, 3, 4} whose underlying when +( 1) = +( 3) = { 2}. Hence, (N3) holds also in undirected graph is a 4. They are the following ten dithe case when |( )⃖⃗| > 1 . graphs:
A straightforward consequence of Proposition 3.7 is a characterization of the 2-qBMGs on three vertices whose underlying undirected graph is a 3 path-graph.
Corollary 3.8. The non-isomorphic 2-qBMGs on three vertices whose underlying undirected graph is a 3 pathgraph are all bipartite digraphs with at least two edges except for a symmetric edge. ( ⃖⃗4(1)) = { 1 2, 1 4, 2 1, 2 3, 3 4, 4 3}, ( ⃖⃗4(2)) = { 1 2, 1 4, 2 3, 3 2, 3 4, 4 3}, ( ⃖⃗4(3)) = { 1 2, 1 4, 3 2, 3 4}, ( ⃖⃗4(4)) = { 1 2, 1 4, 3 2, 4 3}, ( ⃖⃗4(5)) = { 1 2, 2 1, 3 2, 3 4, 4 1}, ( ⃖⃗4(6)) = { 1 2, 1 4, 3 2, 4 1, 4 3}, ( ⃖⃗4(7)) = { 1 2, 1 4, 2 3, 4 3}, ( ⃖⃗4(8)) = { 1 2, 1 4, 3 2, 3 4, 4 3},
The same setup and arguments from the proof of Theorem 3.1 can be used to deal with induced 6-cycles in ( ⃖⃗4(9)) = { 1 2, 1 4, 2 1, 2 3, 3 2, 3 4}, 2-qBMGs since the proof of Theorem 3.1 involves neither ( ⃖⃗4(10)) = { 1 2, 1 4, 3 2, 3 4, 2 1, 2 3, 4 1, 4 3}. 1 6 nor 6 1. Therefore, the following result holds. 13 Theorem 3.9. The underlying undirected graph of any 2-qBMG is 6-free.
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 sets.
Recall that a connected 2-qBMG is of type (A) if its undirected underlying graph has a vertex decomposition into a biclique and a stable set. It may be observed that such a biclique is necessarily a dominating set. ⃖Γ⃗ can be labelled with { 1, 2, … , } such that ∈ ( ⃖Γ⃗) implies < for 1 ≤ , ≤ . In particular, for , ∈ (Δ) of diferent color, either
or is an edge of ⃖Δ⃗.
Therefore, (N1) trivially holds for ⃖Δ⃗ while (N2) follows from the transitivity of the ordering. To show (N3), take a common out-neighbour ∈
⃖Δ⃗. Then is a common out-neighbour of and in ⃖⃗. From (N3) applied to with edge-set Example 4.1. The digraph on 10 vertices { 1, 2, … , 10} , ∈ (Δ) of the same color such that and have ( )⃖⃗= { 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 graph has an induced dominating subgraph with vertex set { 1, 2, 3, 4, 5, 6, 7, 8} and stable set { 9, 10}.
Theorem 4.2. Every connected 2-qBMG has a vertex decomposition into connected 2-qBMGs of type (A). Proof. Let ⃖⃗ be a connected 2-qBMG not of type (A). Let be the underlying undirected graph of ⃖⃗, where and
are its color classes. As mentioned in the introduction, from [15, Theorem 1], contains a dominating biclique Δ with vertex set ∪ where ⊆
and ⊆ ⃖Δ⃗ be the directed subgraph of ⃖⃗ induced by Δ. Let be
. Let the subset of () which +( ) ∪ consisting of all vertices ∈ ()
for −( ) is contained in ∪ . Let ⃖Σ⃗ be the induced subgraph of ⃖⃗on ∪ ∪
. Since Δ is a dominating set of , ⃖Σ⃗ is connected without isolated vertex and is a connected 2-qBMG. The underlying undirected graph Σ of ⃖Σ⃗ is a ⊕ graph, where = ∪
.
Furthermore, let ⃖⃗1 be the induced subgraph of ⃖⃗ on () ⧵ ( ∪ ∪ )
. By construction, no vertex of ⃖⃗1 is isolated, although some vertex of ⃖⃗ may become a sink in ⃖⃗1, and non-equivalent vertices ⃖⃗ may become equivalent in ⃖⃗1. If 1 is not a connected 2-qBMG of type (A), we can repeat the above construction to define a ifnite sequence Σ1, 2, Σ2 … , Σ such that ⃖Σ⃗, ⃖Σ⃗1, ⃖Σ⃗2, … , ⃖Σ⃗ form a vertex partition of ⃖⃗ into connected 2-qBMGs of type (A).
members of the subsequence 1, 2, … , −1 decomposition is not connected, say , applying the above argument on each of the connected components of gives the claimed partition. Proposition 4.3. Let ⃖⃗ be a 2-qBMG satisfying at least one of conditions (∗) and (∗∗). Fix an orientation ⃖Γ⃗ of ⃖⃗. Let ⃖Δ⃗ be an induced subgraph of ⃖Γ⃗ such that the underlying undirected graph Δ is a biclique of . If ⃖⃗has no symmetric edges in ⃖Δ⃗ then ⃖Δ⃗ is a 2-qBMG.
Proof. Let be the number of the vertices of ⃖⃗ (and of ⃖Γ⃗). As pointed out in Section 2, if either (∗) or (∗∗) holds then ∈ ( ⃖Δ⃗). Then ∈ ( )⃖⃗ , and hence ∈ ( )⃖⃗ . Since is not a symmetric edge in ⃖⃗, this yields ∈ ( ⃖Γ⃗) whence ∈ ( ⃖Δ⃗) follows. Thus ⃖Δ⃗ is a 2-qBMG. Theorem 4.4. Let ⃖⃗ be a connected 2-qBMG satisfying (∗). Then ⃖⃗ has an even-odd subgraph (, ) underlying undirected subgraph of (, ) such that the is a dominating biclique of .
Proof. Fix an orientation ⃖Γ⃗ of ⃖⃗ by keeping the same vertex set but retaining exactly one edge from each symmetric edge. Let be the underlying undirected graph of ⃖⃗. Then coincides with the underlying undirected graph of ⃖Γ⃗. As mentioned in Introduction, from [15, Theorem 1], contains a dominating biclique Δ with vertex set ∪ where ⊆ and ⊆ where and are the bipartion classes of . Let ⃖Δ⃗ be the directed subgraph on vertex-set ∪
where ∈ ( ⃖Δ⃗) if and only if is an edge of ⃖Γ⃗. It should be noticed that ⃖Δ⃗ may not be the induced subgraph of ⃖⃗ on the vertex-set ∪ . This occurs indeed when ⃖⃗contains a symmetric edge with both endpoints in ∪ . Nevertheless, ⃖Δ⃗ is bitournament. Since ⃖Δ⃗ is bitransitive, it is an even-odd digraph, as recalled in
The 6-and 6-freeness in the undirected underlying 2qBMGs raises the problem of finding more such forbidden subgraphs on six (or eight) vertices. In this direction, the domino graph on six vertices (i.e. the Cartesian product 2 × 3) and its generalization on eight vertices, the longdomino or ladder graph, appearworth investigating.
In [20], bipartite 6 and 6-free graphs are characterized as those graphs where every connected subgraph is of type ⊕ . This gives rise to a linear time algorithm for recognizing if an undirected graph is 6 and 6-free by tracing all ⊕
decompositions. It would be interesting to investigate whether a similar approach can be 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 insome 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 biparcover problem for the family of underlying undirected tite subgraphs in graphs, Discussiones Mathematigraphs 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, BiPadilla, 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 FoundaRevolutionh-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, iftte, 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.