Different Duality Theorems

Abstract

Given a (directed) graph \(G = (V,A)\), the induced subgraph of \(G\) by a subset \(X\) of \(V\) is denoted by \(G[X]\). A graph \(G = (V, A)\) is a \({tournament}\) if for any distinct vertices \(x\) and \(y\) of \(G\), \(G[\{x, y\}]\) possesses a single arc. With each graph \(G = (V,A)\), associate its \({dual}\) \(G^* = (V, A^*)\) defined as follows: for \(x,y \in V\), \((x,y) \in A^*\) if \((y,x) \in A\). Two graphs \(G\) and \(H\) are \({hemimorphic}\) if \(G\) is isomorphic to \(H\) or to \(H^*\). Moreover, let \(k > 0\). Two graphs \(G = (V,A)\) and \(H = (V,B)\) are \({k\;-hemimorphic}\) if for every \(X \subseteq V\), with \(|X| \leq k\), \(G[X]\) and \(H[X]\) are hemimorphic. A graph \(G\) is \({k\;-forced}\) when \(G\) and \(G^*\) are the only graphs \(k\)-hemimorphic to \(G\). Given a graph \(G = (V,A)\), a subset \(X\) of \(V\) is an \({interval}\) of \(G\) provided that for \(a,b \in X\) and \(x \in V\setminus X\), \((a,x) \in A\) if and only if \((b,x) \in A\), and similarly for \((x,a)\) and \((x,b)\). For example, \(\emptyset\), \(\{x\}\), where \(x \in V\), and \(V\) are intervals called trivial. A graph \(G = (V, A)\) is \({indecomposable}\) if all its intervals are trivial. Boussairi, Tle, Lopez, and Thomassé \([2]\) established the following duality result. An indecomposable graph which does not contain the graph \(({0, 1, 2}, {(0, 1), (1,0), (1,2)})\) and its dual as induced subgraphs is \(3\)-forced. A simpler proof of this theorem is provided in the case of tournaments and also in the general case. The \(3\)-forced graphs are then characterized.