Structural properties of CKI-digraphs (Q2512568): Difference between revisions

Let \(D=(V(D),A(D))\) be a digraph then \(X\subseteq V(D)\) is called a kernel of \(D\) if \((x,y)\notin A(D)\) for all \(x,y\in V(D)\) and for every \(x\in V(D)\setminus X\) there exists \(y\in X\) with \((x,y)\in A(D)\). A digraph is a CKI-digraph if \(D\) has no kernel and every proper induced subgraph of \(D\) has a kernel, \(D\) is kernel perfect if every induced subgraph of \(D\) (including \(D\)) has a kernel and \(D\) is kernel critical if \(D\) has no kernel and \(D\setminus \{x\}\) has a kernel for every \(x\in V(D)\). The paper proves that if \(D\) is a CKI-digraph then \(D\setminus a\) is kernel perfect for every bridge \(a\in A(D)\). If \(D\) is an asymmetric CKI-digraph of size \( n\) then for every \(u\in V(D)\) the sum of the outdegree of \(u\) and the indegree of \(u\) is at most \(n-3\), \(|A(D)|\leq\frac {n(n-3)}2\) and the maximum outdegree of \(D\) and the maximum indegree of \(D\) are at most \(n-5\). If \(D\) is a kernel critical digraph then any kernel of \(D\setminus \{x\}\) has at least two vertices for all \(x\in V(D)\) and one of the following conditions holds: every directed triangle of \(D\) has at least two symmetric arcs; \(D\) is free of directed triangles. Some consequences for CKI-digraphs of small size (less than 10) are derived. The relations between tournaments and CKI-digraphs are presented.