Minimal indecomposable graphs (Q1382817)

A finite (directed) graph \(G=(V,E)\) is symmetric (resp. a tournament) whenever for \(x\neq y\in V\), \((x,y)\in E\Leftrightarrow (y,x)\in E\) (resp. \((x,y)\in E\Leftrightarrow (y,x) \notin E)\). \(G=(V,E)\) is a poset whenever for \(x\neq y\in V\), \((x,y)\in E\Rightarrow (y,x) \notin E\) and for \(x,y,z\in V\), \((x,y)\), \((y,z)\in E\Rightarrow (x,z)\in E\). \(A\) poset \(G\) is a linear ordering when for \(x\neq y\), \((x,y)\in E\) or \((y,x)\in E\). A subset \(X\) of \(V\) is an interval of \(G\) whenever for \(a,b\in X\) and \(x\in V-X\), the ordered pairs \((a,x)\) and \((b,x)\) are equivalent. Given a graph \(G=(V,E)\) then \(\varnothing\), \(V\) and \(\{x\}\), where \(x\in V\), are called trivial intervals, and \(G\) is said to be indecomposable whenever all of its intervals are trivial. A graph \(G=(V,E)\), which admits at least an interval \(X\) such that \(2\leq| X| <| V|\), is said to be decomposable. An indecomposable graph \(G=(V,E)\) is minimal for elements \(x_1, \dots, x_k\) of \(V\) when for each \(Y\subset V\) \((Y\neq V)\) such that \(\{x_1, \dots, x_k\} \subseteq Y\) and \(| Y|\geq 3\), the induced subgraph \(G(Y)\) of \(G\) is decomposable. In the present paper the minimal indecomposable graphs of one or two vertices are characterized, and especially minimal indecomposable symmetric graphs, posets and tournaments are described. Therefore, in Section 2, properties of indecomposable graphs are given which are used for these investigations. At first, minimal indecomposable symmetric graphs are investigated in Section 3 and therefore certain graphs \(P_4\), \(Q_5\) and extensions \(P_k\), \(Q_k\) of them \((k\geq 4)\) are introduced and also given vividly by figures. Then the authors prove the results that for an indecomposable symmetric graph \(G=(V,E)\) with \(| V|\geq 4\), (1) \(G\) is minimal for \(x\in V\) iff either \(G\) is isomorphic to \(P_4\) or there is an isomorphism \(f\) from \(G\) to \(Q_5\) such that \(f(x)=1\) (Corollary 2), and (2) \(G\) is minimal for distinct elements \(x,y\) of \(V\) iff there is an isomorphism \(f\) from \(G\) or its complement \(\overline G\) onto \(P_k\) or \(Q_k\) (where \(k\geq 4)\) such that \(f(\{x,y\}) =\{1,k\}\) (Theorem 2). The most extensive Section 4 contains investigations of the general case. To characterize minimal indecomposable graphs of one vertex, the authors introduce the concept of transitive orientation of a graph (Definition 2), especially of \(P_4\) and \(Q_5\), and so they get, by Corollary 3, a generalisation of Corollary 2. To characterize minimal indecomposable graphs of two vertices, generalisations of \(P_k\) and \(Q_k\) are needed and families of certain graphs are defined (Definitions 3 and 4); the result (Theorem 6), received by an extensive proof, is a generalisation of Theorem 2. Finally the minimal indecomposable posets and tournaments of two vertices are described and, by using theorems of the present paper, the authors get results given in Corollaries 4 to 7.