k-kernels in generalizations of transitive digraphs

Hortensia Galeana-Sánchez; César Hernández-Cruz

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 293-312
  • ISSN: 2083-5892

Abstract

top
Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N, u ≠ v, then d(u,v), d(v,u) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. Quasi-transitive, right-pretransitive and left-pretransitive digraphs are generalizations of transitive digraphs. In this paper the following results are proved: Let D be a right-(left-) pretransitive strong digraph such that every directed triangle of D is symmetrical, then D has a k-kernel for every integer k ≥ 3; the result is also valid for non-strong digraphs in the right-pretransitive case. We also give a proof of the fact that every quasi-transitive digraph has a (k,l)-kernel for every integers k > l ≥ 3 or k = 3 and l = 2.

How to cite

top

Hortensia Galeana-Sánchez, and César Hernández-Cruz. "k-kernels in generalizations of transitive digraphs." Discussiones Mathematicae Graph Theory 31.2 (2011): 293-312. <http://eudml.org/doc/270821>.

@article{HortensiaGaleana2011,
abstract = { Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N, u ≠ v, then d(u,v), d(v,u) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. Quasi-transitive, right-pretransitive and left-pretransitive digraphs are generalizations of transitive digraphs. In this paper the following results are proved: Let D be a right-(left-) pretransitive strong digraph such that every directed triangle of D is symmetrical, then D has a k-kernel for every integer k ≥ 3; the result is also valid for non-strong digraphs in the right-pretransitive case. We also give a proof of the fact that every quasi-transitive digraph has a (k,l)-kernel for every integers k > l ≥ 3 or k = 3 and l = 2. },
author = {Hortensia Galeana-Sánchez, César Hernández-Cruz},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {digraph; kernel; (k,l)-kernel; k-kernel; transitive digraph; quasi-transitive digraph; right-pretransitive digraph; left-pretransitive digraph; pretransitive digraph; -kernel; -kernel},
language = {eng},
number = {2},
pages = {293-312},
title = {k-kernels in generalizations of transitive digraphs},
url = {http://eudml.org/doc/270821},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - César Hernández-Cruz
TI - k-kernels in generalizations of transitive digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 293
EP - 312
AB - Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. A (k,l)-kernel N of D is a k-independent set of vertices (if u,v ∈ N, u ≠ v, then d(u,v), d(v,u) ≥ k) and l-absorbent (if u ∈ V(D)-N then there exists v ∈ N such that d(u,v) ≤ l). A k-kernel is a (k,k-1)-kernel. Quasi-transitive, right-pretransitive and left-pretransitive digraphs are generalizations of transitive digraphs. In this paper the following results are proved: Let D be a right-(left-) pretransitive strong digraph such that every directed triangle of D is symmetrical, then D has a k-kernel for every integer k ≥ 3; the result is also valid for non-strong digraphs in the right-pretransitive case. We also give a proof of the fact that every quasi-transitive digraph has a (k,l)-kernel for every integers k > l ≥ 3 or k = 3 and l = 2.
LA - eng
KW - digraph; kernel; (k,l)-kernel; k-kernel; transitive digraph; quasi-transitive digraph; right-pretransitive digraph; left-pretransitive digraph; pretransitive digraph; -kernel; -kernel
UR - http://eudml.org/doc/270821
ER -

References

top
  1. [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag Berlin Heidelberg New York, 2002). Zbl1001.05002
  2. [2] J. Bang-Jensen and J. Huang, Quasi-transitive digraphs, J. Graph Theory 20 (1995) 141-161, doi: 10.1002/jgt.3190200205. Zbl0832.05048
  3. [3] J. Bang-Jensen and J. Huang, Kings in quasi-transitive digraphs, Discrete Math. 185 (1998) 19-27, doi: 10.1016/S0012-365X(97)00179-9. Zbl0955.05048
  4. [4] C. Berge, Graphs (North-Holland, Amsterdam New York, 1985). 
  5. [5] C. Berge, Some classes of perfect graphs, in: Graph Theory and Theoretical Physics (Academic Press, London, 1967) 155-165, MR 38 No. 1017. 
  6. [6] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31, doi: 10.1016/0012-365X(90)90346-J. Zbl0721.05027
  7. [7] E. Boros and V. Gurvich, Perfect graphs are kernel solvable, Discrete Math. 159 (1996) 35-55, doi: 10.1016/0012-365X(95)00096-F. Zbl0861.05053
  8. [8] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The Strong Perfect Graph Theorem, Annals of Math. 164 (2006) 51-229. Zbl1112.05042
  9. [9] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag Berlin Heidelberg New York, 2005). 
  10. [10] P. Duchet, Graphes Noyau-Parfaits, Annals of Discrete Math. 9 (1980) 93-101, doi: 10.1016/S0167-5060(08)70041-4. 
  11. [11] H. Galeana-Sánchez, On the existence of kernels and h-kernels in directed graphs, Discrete Math. 110 (1992) 251-255, doi: 10.1016/0012-365X(92)90713-P. Zbl0770.05050
  12. [12] H. Galeana-Sánchez and R. Rojas-Monroy, Kernels in quasi-transitive digraphs, Discrete Math. 306 (2006) 1969-1974, doi: 10.1016/j.disc.2006.02.015. Zbl1100.05042
  13. [13] A. Ghouila-Houri, Caractérization des graphes non orientés dont on peut orienter les arretes de maniere a obtenir le graphe dune relation dordre, Comptes Rendus de l'Académie des Sciences Paris 254 (1962) 1370-1371. Zbl0105.35503
  14. [14] I. Golfeder, (k,l)-kernels in quasi-transitive digraphs, Instituto de Matemáticas de la Universidad Nacional Autónoma de México, Publicación preliminar 866 (2009). 
  15. [15] M. Kucharska and M. Kwaśnik, On (k,l)-kernels of special superdigraphs of Pₘ and Cₘ, Discuss. Math. Graph Theory 21 (2001) 95-109, doi: 10.7151/dmgt.1135. 
  16. [16] M. Kwaśnik, On (k,l)-kernels on Graphs and Their Products, Doctoral dissertation (Technical University of Wrocław, Wrocław, 1980). 
  17. [17] M. Kwaśnik, The Generalizaton of Richardson's Theorem, Discuss. Math. 4 (1981) 11-14. 
  18. [18] V. Neumann-Lara, Semin'ucleos de una digráfica, Anales del Instituto de Matemáticas II (1971). 
  19. [19] M. Richardson, On Weakly Ordered Systems, Bull. Amer. Math. Soc. 52 (1946) 113-116, doi: 10.1090/S0002-9904-1946-08518-3. Zbl0060.06506
  20. [20] W. Szumny, A. Włoch and I. Włoch, On (k,l)-kernels in D-join of digraphs, Discuss. Math. Graph Theory 27 (2007) 457-470, doi: 10.7151/dmgt.1373. Zbl1142.05040
  21. [21] W. Szumny, A. Włoch and I. Włoch, On the existence and on the number of (k,l)-kernels in the lexicographic product of graphs, Discrete Math. 308 (2008) 4616-4624, doi: 10.1016/j.disc.2007.08.078. Zbl1169.05039
  22. [22] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1953). Zbl0053.09303
  23. [23] A. Włoch and I. Włoch, On (k,l)-kernels in generalized products, Discrete Math. 164 (1997) 295-301. 

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.