Discussiones Mathematicae Graph Theory 27(3) (2007) 389-400
doi: 10.7151/dmgt.1369

[BIBTex] [PDF] [PS]

MONOCHROMATIC KERNEL-PERFECTNESS OF SPECIAL CLASSES OF DIGRAPHS

Hortensia Galeana-Sánchez

Instituto de Matemáticas
Universidad Nacional Autónoma de México
Ciudad Universitaria, México, D.F. 04510, México

Luis Alberto Jiménez Ramírez

Facultad de Ciencias
Universidad Nacional Autónoma de México
Ciudad Universitaria, México, D.F. 04510, México

Abstract

In this paper, we introduce the concept of monochromatic kernel-perfect digraph, and we prove the following two results:

(1) If D is a digraph without monochromatic directed cycles, then D and each αv,v ∈ V(D) are monochromatic kernel-perfect digraphs if and only if the composition over D of (αv)v ∈ V(D) is a monochromatic kernel-perfect digraph.

(2) D is a monochromatic kernel-perfect digraph if and only if for any B ⊆ V(D), the duplication of D over B, DB, is a monochromatic kernel-perfect digraph.

Keywords: kernel, kernel by monochromatic paths, composition, duplication.

2000 Mathematics Subject Classification: 05C20.

References

[1] C. Berge, Graphs (North-Holland, Amsterdam, 1985).
[2] M. Blidia, P. Duchet, H. Jacob, F. Maffray and H. Meyniel, Some operations preserving the existence of kernels, Discrete Math. 205 (1999) 211-216, doi: 10.1016/S0012-365X(99)00026-6.
[3] M. Borowiecki and A. Szelecka, One-factorizations of the generalized Cartesian product and of the X-join of regular graphs, Discuss. Math. Graph Theory 13 (1993) 15-19.
[4] M. Burlet and J. Uhry, Parity Graphs, Annals of Discrete Math. 21 (1984) 253-277.
[5] P. Duchet and H. Meyniel, A note on kernel-critical graphs, Discrete Math. 33 (1981) 103-105, doi: 10.1016/0012-365X(81)90264-8.
[6] H. Galeana-Sánchez and V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67-76, doi: 10.1016/0012-365X(84)90131-6.
[7] H. Galeana-Sánchez, On monochromatic paths and monochromatics cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-110, doi: 10.1016/0012-365X(95)00036-V.
[8] H. Galeana-Sánchez and V. Neumann-Lara, On the dichromatic number in kernel theory, Math. Slovaca 48 (1998) 213-219.
[9] H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and monochromatic 4-cycles in edge-coloured bipartite tournaments, Discrete Math. 285 (2004) 313-318, doi: 10.1016/j.disc.2004.03.005.
[10] G. Hahn, P. Ille and R.E. Woodrow, Absorbing sets in arc-coloured tournaments, Discrete Math. 283 (2004) 93-99, doi: 10.1016/j.disc.2003.10.024.
[11] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combinatoria 60 (2001) 137-147.
[12] M. Kucharska, On (k,l)-kernel perfectness of special classes of digraphs, Discussiones Mathematicae Graph Theory 25 (2005) 103-119, doi: 10.7151/dmgt.1265.
[13] M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573, doi: 10.2307/1969755.
[14] S. Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7.
[15] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8.
[16] J. von Neumann and O. Morgenstern, Theory of games and economic behavior (Princeton University Press, Princeton, 1944).
[17] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301, doi: 10.1016/S0012-365X(96)00064-7.
[18] I. Włoch, On kernels by monochromatic paths in the corona of digraphs, preprint.

Received 17 January 2006
Revised 11 June 2007
Accepted 11 June 2007