Download Poster (119 KB)
Let D = (V, E) be a digraph. A subset K of V is a quasi-kernel of D if K is an independent set in D and for every vertex v belonging to the set V – K, v is at most a distance of 2 from K. It is a well-known result of Chvátal and Lovász that every digraph has a quasi-kernel. In 1976, P. L. Erdős and L. A. Székely conjectured that if every vertex of D has a positive in-degree, then D has a quasi-kernel of size at most half the order of D. A tournament is obtained from a complete graph by assigning a direction to each edge, and a hairy tournament is a digraph whose deletion of all sink vertices yields a tournament, where a sink vertex is a vertex of zero out-degree. A core is the largest tournament of a hairy tournament. In this work, we study the size of a quasi-kernel in a hairy tournament and support the Erdős-Székely conjecture for hairy tournaments such that each vertex of its core is joined to at most two sink vertices.
Let G be a n-vertex hairy tournament, let T contained within G be the core of G. If for every v in V(T), v is joined to at most two sink vertices of G that belong to V(G) – V(T), then G has a quasi-kernel of size at most half n.
This Theorem implies that given an n-vertex hairy tournament in which the core is joined to no more than two sink vertices, one can find an independent set K of G satisfying two properties: for any x belonging to V(G) - K it holds that distG(K,x) ≤ 2, and the number of vertices in K will be at most half n.
In essence, our proof is an application of induction on the number of edges of G, or equivalently, by taking a counter example G with the smallest number of edges to the statement, and then finding a way to reduce the graph to one G* with a smaller number of edges. As G* is no longer a counterexample to the statement, a desired quasi-kernel K* of G* can be found. We then modify K* to get a desired quasi-kernel for G. In order to accomplish this, we begin by investigating the structures of a counterexample with the smallest number of edges to the statement. We prove two essential properties regarding the in-degree values of sink vertices and how those sink vertices relate to the tournament part of the graph.
Hayes-Carver, Jesse and Witt, Walter J., "Small Quasi-Kernels in Hairy Tournaments" (2020). Mathematics. 3.