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

Discussiones Mathematicae Graph Theory (2013)

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

## Access Full Article

top## Abstract

top## How to cite

topRuixia 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] J. Bang-Jensen, Kings in quasi-transitive digraphs, Discrete Math. 185 (1998) 19-27. doi:10.1016/S0012-365X(97)00179-9[Crossref]
- [2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000). Zbl0958.05002
- [3] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012) 205-219. doi:10.7151/dmgt.1613[Crossref]
- [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] 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] 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] 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

## Citations in EuDML Documents

top## NotesEmbed ?

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