A new sufficient condition for the existence of 3-kernels

• Alonso Ali UNICAMP
• Orlando Lee UNICAMP

DOI: https://doi.org/10.5753/etc.2020.11083

Resumo

Let D be a digraph and k be a positive integer. We say a subset N of V(D) is a k-kernel of D if it is both k-independent and (k − 1)-absorbent. A short chord of a closed trail C = (v0, v1, . . . , vt) is an arc a = (vi, vj) which does not belong to C and the distance from vi to vj in C is exactly two. The spacing between two chords e = (u, v) and f = (x, y) in C is the distance from u to x in C. A set of chords in a closed trail C has an odd spacing if at least two chords have an odd spacing. In this work, we prove that if D is a strongly connected digraph where every odd cycle has a short chord and every even closed trail has three short chords with an odd spacing, then D has a 3-kernel.

Palavras-chave: k-kernel, kernel, chord, cycle

Referências

Bondy, J. and Murty, U. (2008). Graph Theory. Springer Publishing Company, Incorporated, 1st edition.

Duchet, P. (1980). Graphes noyau-parfaits. Ann. Discrete Math., 9:93–101. Combinatorics 79 (Proc. Colloq., Univ. Montreal, Montreal, Que., 1979), Part II.

Galeana-Sanchez, H. and Hernández-Cruz, C. (2014). On the existence of (k, l)-kernels in infinite digraphs: A survey. Discussiones Mathematicae Graph Theory, 34(3):431–466.

Kwasnik, M. (1980). On (k, l)-kernels on graphs and their products. PhD thesis, Technical University of Wroclaw.

Kwasnik, M. (1981). The generalization of richardson theorem. Discuss. Math., IV:11–13.

von Neumann, J. and Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey.