Indecomposable graphs (Q1367028): Difference between revisions

Let \(G= (V,E)\) be a finite directed graph. A subset \(X\) of \(V\) is an interval of \(G\) if for \(a,b\in X\) and \(x\in V-X\), we have \(ax\in E\) (resp. \(xa\in E\)) if and only if \(bx\in E\) (resp. \(xb\in E\)). So \(\varnothing\), \(V\) and every singleton are intervals of \(G\) (called trivial intervals). The graph \(G\) is said to be indecomposable if every interval of \(G\) is trivial. Let \(G\) be an indecomposable graph, let \(X\) be a subset of \(V\) such that \(|X|\geq 3\) and \(|V-X|\geq 6\), and let \(G(X)\) be indecomposable. This paper proves that there is a subset \(Y\) of \(V\) such that \(X\subseteq Y\), \(|V-Y|=2\), and \(G(Y)\) is indecomposable.