Domination graphs with nontrivial components (Q5943042): Difference between revisions

A tournament is an oriented complete graph. Vertices \(x\) and \(y\) dominate a tournament \(T\) if for all vertices \(z \neq x, y\), either \((x, z)\) or \((y, z)\) are arcs in \(T\) (possibly both). The domination graph of a tournament \(T\) is the graph on the vertex set of \(T\) containing edge \(\{x, y\}\) if and only if \(x\) and \(y\) dominate \(T\). A spiked cycle is a graph whose non-pendant vertices induce a cycle. A caterpillar is \(K_1\) or \(K_2\) or a graph of order at least 3 whose non-pendant vertices induce a path called its spine. We say a caterpillar of order at least 5 has a triple end if it is \(K_{1, n}\) for \(n \geq 4\) or if at least one of the end vertices on the spine has degree at least 4. The authors use results from other papers to completely characterize domination graphs of tournaments. In particular they show that a graph \(G\) with \(n\) components is the domination graph of a tournament if and only if \(n=1\) and \(G\) is a spiked odd cycle, a star or a caterpillar with a triple end or \(n \geq 2\), each component is a caterpillar and one of the following occurs: (i) \(n=2\) and either both caterpillars have a triple end or one has a triple end and the other is \(K_{1, 3}\); (ii) \(n=3\) and either all three caterpillars have a triple end, or one caterpillar is \(K_{1, 3}\) and the other two have a triple end; (iii) \(n=5\) and at least one of the caterpillars has a triple end or is a \(K_{1,3}\); and (iv) \(n=4\) or \( n \geq 6\).