Independent transversals of longest paths in locally semicomplete and locally transitive digraphs

Hortensia Galeana-Sánchez; Ricardo Gómez; Juan José Montellano-Ballesteros

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 3, page 469-480
  • ISSN: 2083-5892

Abstract

top
We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.

How to cite

top

Hortensia Galeana-Sánchez, Ricardo Gómez, and Juan José Montellano-Ballesteros. "Independent transversals of longest paths in locally semicomplete and locally transitive digraphs." Discussiones Mathematicae Graph Theory 29.3 (2009): 469-480. <http://eudml.org/doc/271050>.

@article{HortensiaGaleana2009,
abstract = {We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.},
author = {Hortensia Galeana-Sánchez, Ricardo Gómez, Juan José Montellano-Ballesteros},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {independent set; longest path; locally semicomplete; locally transitive},
language = {eng},
number = {3},
pages = {469-480},
title = {Independent transversals of longest paths in locally semicomplete and locally transitive digraphs},
url = {http://eudml.org/doc/271050},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - Ricardo Gómez
AU - Juan José Montellano-Ballesteros
TI - Independent transversals of longest paths in locally semicomplete and locally transitive digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 469
EP - 480
AB - We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.
LA - eng
KW - independent set; longest path; locally semicomplete; locally transitive
UR - http://eudml.org/doc/271050
ER -

References

top
  1. [1] J. Bang-Jensen, Locally semicomplete digraphs: A generalization of tournaments, J. Graph Theory 14 1990) 371-390, doi: 10.1002/jgt.3190140310. 
  2. [2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer Monographs in Mathematics, 2001). Zbl0958.05002
  3. [3] J. Bang-Jensen and G. Gutin, Generalization of tournaments: A survey, J. Graph Theory 14 (1998) 371-390, doi: 10.1002/jgt.3190140310. Zbl0920.05033
  4. [4] J. Bang-Jensen, M.H. Nielsen and A. Yeo, Longest path partitions in generalizations of tournaments, Discrete Math. 306 (2006) 1830-1839, doi: 10.1016/j.disc.2006.03.063. Zbl1103.05036
  5. [5] E. Boros and V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete Math. 306 (2006) 2336-2354, doi: 10.1016/j.disc.2005.12.031. Zbl1103.05034
  6. [6] V. Chvátal and L. Lovász, Every directed graph has a semi-kernel, Lecture Notes in Math. Vol. 411 (Springer, Berlin, 1974). Zbl0297.05116
  7. [7] M. Frick, S. Van Aardt, G. Dlamini, J. Dunbar and O. Oellermann, The directed path partition conjecture, Discuss. Math. Graph Theory 25 (2005) 331-343, doi: 10.7151/dmgt.1286. Zbl1118.05040
  8. [8] M. Frick, S. Van Aardt, J. Dunbar, M. Nielsen and O. Oellermann, A traceability conjecture for oriented graphs, The Electronic Journal of Combinatorics 15 (2008) #R150. Zbl1178.05046
  9. [9] H. Galeana-Sánchez and R. Gómez, Independent sets and non-augmentable paths in generalization of tournaments, Discrete Math. 308 (2008) 2460-2472, doi: 10.1016/j.disc.2007.05.016. Zbl1147.05042
  10. [10] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest paths in digraphs, in: Graphs and other combinatorial topics, Proceedings of the Third Czechoslovak Symposium of Graph Theory (1982) 173-177. 

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.