Monochromatic kernel-perfectness of special classes of digraphs

Hortensia Galeana-Sánchez; Luis Alberto Jiménez Ramírez

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 3, page 389-400
  • ISSN: 2083-5892

Abstract

top
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, D B , is a monochromatic kernel-perfect digraph.

How to cite

top

Hortensia Galeana-Sánchez, and Luis Alberto Jiménez Ramírez. "Monochromatic kernel-perfectness of special classes of digraphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 389-400. <http://eudml.org/doc/270413>.

@article{HortensiaGaleana2007,
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, $D^B$, is a monochromatic kernel-perfect digraph.},
author = {Hortensia Galeana-Sánchez, Luis Alberto Jiménez Ramírez},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; kernel by monochromatic paths; composition; duplication; monochromatic paths},
language = {eng},
number = {3},
pages = {389-400},
title = {Monochromatic kernel-perfectness of special classes of digraphs},
url = {http://eudml.org/doc/270413},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - Luis Alberto Jiménez Ramírez
TI - Monochromatic kernel-perfectness of special classes of digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 389
EP - 400
AB - 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, $D^B$, is a monochromatic kernel-perfect digraph.
LA - eng
KW - kernel; kernel by monochromatic paths; composition; duplication; monochromatic paths
UR - http://eudml.org/doc/270413
ER -

References

top
  1. [1] C. Berge, Graphs (North-Holland, Amsterdam, 1985). 
  2. [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. Zbl0936.05047
  3. [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. Zbl0794.05099
  4. [4] M. Burlet and J. Uhry, Parity Graphs, Annals of Discrete Math. 21 (1984) 253-277 Zbl0558.05036
  5. [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. Zbl0456.05032
  6. [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. Zbl0529.05024
  7. [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. [8] H. Galeana-Sánchez and V. Neumann-Lara, On the dichromatic number in kernel theory, Math. Slovaca 48 (1998) 213-219. Zbl0937.05048
  9. [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. Zbl1049.05042
  10. [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. Zbl1042.05049
  11. [11] M. Kucharska, On (k,l)-kernels of orientations of special graphs, Ars Combinatoria 60 (2001) 137-147. Zbl1068.05504
  12. [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. Zbl1074.05043
  13. [13] M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953) 573, doi: 10.2307/1969755. Zbl0053.02902
  14. [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. Zbl0654.05033
  15. [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. Zbl0488.05036
  16. [16] J. von Neumann and O. Morgenstern, Theory of games and economic behavior (Princeton University Press, Princeton, 1944). Zbl0063.05930
  17. [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. [18] I. Włoch, On kernels by monochromatic paths in the corona of digraphs, preprint. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.