Title

Small Quasi-Kernels in Hairy Tournaments

Author

Jesse Hayes-Carver, UndergraduateFollow
Walter J. Witt, UndergraduateFollow

Files

Publication Date

4-2020

Document Type

Poster

Presentation Type

Group

Department

Mathematics

Mentor

Songling Shan

Mentor Department

Mathematics

Abstract

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.

Theorem

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 dist_G(K,x) ≤ 2, and the number of vertices in K will be at most half n.

Methods

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.

Notes

Authors: Jesse Hayes-Carver, Walter J. Witt

This project has not received IRB approval.

Recommended Citation

Hayes-Carver, Jesse and Witt, Walter J., "Small Quasi-Kernels in Hairy Tournaments" (2020). Mathematics. 3.
https://ir.library.illinoisstate.edu/ursmat/3