PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 4 | 651-671
Tytuł artykułu

Some Remarks On The Structure Of Strong K-Transitive Digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.
Wydawca
Rocznik
Tom
34
Numer
4
Strony
651-671
Opis fizyczny
Daty
wydano
2014-11-01
otrzymano
2012-05-07
poprawiono
2013-07-15
zaakceptowano
2013-08-06
online
2014-11-15
Twórcy
  • Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, México, D.F., C.P. 04510, México, cesar@matem.unam.mx
  • Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, México, D.F., C.P. 04510, México, juancho@matem.unam.mx
Bibliografia
  • [1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer-Verlag Berlin, Heidelberg New York, 2002).
  • [2] R. Diestel, Graph Theory 3rd Edition (Springer-Verlag Berlin, Heidelberg New York, 2005).
  • [3] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in k-transitive and k-quasi- transitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005
  • [4] A. Ghouila-Houri, Caract´erisation des graphes non orient´es dont on peut orienterles arrˆetes de mani`ere `a obtenir le graphe d’une relation d’ordre, C. R. Acad. Sci. Paris 254 (1962) 1370-1371.
  • [5] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613
  • [6] C. Hernández-Cruz, 4-transitive digraphs I: The structure of strong 4-transitive di- graphs, Discuss. Math. Graph Theory 33 (2013) 247-260. doi:10.7151/dmgt.1645
  • [7] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other Combinatorial Topics, Prague, M. Fiedler (Ed(s)), (Teubner, Leipzig, 1983) 173-177.
  • [8] R. Wang, A conjecture on k-transitive digraphs, Discrete Math. 312 (2012) 1458-1460. doi:0.1016/j.disc.2012.01.011
  • [9] R. Wang and S. Wang, Underlying graphs of 3-quasi-transitive digraphs and 3- transitive digraphs, Discuss. Math. Graph Theory 33 (2013) 429-436. doi:10.7151/dmgt.1680
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1765
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.