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^{\ast }=(V,A^{\ast })$ defined as follows: for $x,y\in V$, $(x,y)\in A^{\ast }$ if $(y,x)\in A$. Two graphs $G$ and $H$ are $hemimorphic$ if $G$ is isomorphic to $H$ or to $H^{\ast }$. Moreover, let $k>0$. Two graphs $G=(V,A)$ and $H=(V,B)$ are $k-hemimorphic$ if for every $X\subseteq V$, with $|X|\le k$, $G[X]$ and $H[X]$ are hemimorphic. A graph $G$ is $k-forced$ when $G$ and $G^{\ast }$ 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, $\mathrm{\varnothing }$, $\{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.