Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs

Ruixia Wang; Shiying Wang

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 429-435
  • ISSN: 2083-5892

Abstract

top
A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). C´esar Hern´andez-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation. In this paper, we shall prove that the conjecture is true.

How to cite

top

Ruixia Wang, and Shiying Wang. "Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs." Discussiones Mathematicae Graph Theory 33.2 (2013): 429-435. <http://eudml.org/doc/267988>.

@article{RuixiaWang2013,
abstract = {A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). C´esar Hern´andez-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation. In this paper, we shall prove that the conjecture is true.},
author = {Ruixia Wang, Shiying Wang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph orientation; 3-quasi-transitive digraph; 3-transitive digraph},
language = {eng},
number = {2},
pages = {429-435},
title = {Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs},
url = {http://eudml.org/doc/267988},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Ruixia Wang
AU - Shiying Wang
TI - Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 429
EP - 435
AB - A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). C´esar Hern´andez-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation. In this paper, we shall prove that the conjecture is true.
LA - eng
KW - graph orientation; 3-quasi-transitive digraph; 3-transitive digraph
UR - http://eudml.org/doc/267988
ER -

References

top
  1. [1] J. Bang-Jensen, Kings in quasi-transitive digraphs, Discrete Math. 185 (1998) 19-27. doi:10.1016/S0012-365X(97)00179-9[Crossref] 
  2. [2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000). Zbl0958.05002
  3. [3] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613[Crossref] 
  4. [4] A. Ghouila-Houri, Caractérization des graphes non orient´es dont onpeut orienter les arrˆetes de mani`ere `aobtenir le graphe dune relation dordre, Comptes Rendus de l’Acad´emie des Sciences Paris 254 (1962) 1370-1371. 
  5. [5] H. Galeana-Sánchez, I.A. Goldfeder and I. Urrutia, On the structure of strong 3- quasi-transitive digraphs, Discrete Math. 310 (2010) 2495-2498. doi:10.1016/j.disc.2010.06.008[WoS][Crossref] Zbl1213.05112
  6. [6] H. Galeana-Sánchez and C. Hernández-Cruz, k-kernels in k-transitive and k-quasitransitive digraphs, Discrete Math. 312 (2012) 2522-2530. doi:10.1016/j.disc.2012.05.005[WoS][Crossref] 
  7. [7] S.Wang and R.Wang, Independent sets and non-augmentable paths in arc-locally insemicomplete digraphs and quasi-arc-transitive digraphs, Discrete Math. 311 (2011) 282-288. doi:10.1016/j.disc.2010.11.009[WoS][Crossref] Zbl1222.05090

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.