#### Files

Download Poster (119 KB)

#### 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.

#### 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

## Notes

Authors: Jesse Hayes-Carver, Walter J. Witt

This project has not received IRB approval.