TITLE

UNDERLYING GRAPHS OF 3-QUASI-TRANSITIVE DIGRAPHS AND 3-TRANSITIVE DIGRAPHS RUIXIA WANG, SHIYING WANG

AUTHOR(S)
RUIXIA WANG; SHIYING WANG
PUB. DATE
July 2013
SOURCE
Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p429
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
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ésar Hernández-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.
ACCESSION #
86720994

 

Related Articles

  • A Contribution to the Second Neighborhood Problem. Ghazal, Salman // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1365 

    Seymour's Second Neighborhood Conjecture asserts that every oriented graph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. It is proved for tournaments, tournaments missing a matching and tournaments missing a generalized star. We...

  • SOME REMARKS ON THE STRUCTURE OF STRONG k-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR; MONTELLANO-BALLESTEROS, JUAN JOSÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p651 

    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...

  • On Sullivan's conjecture on cycles in 4-free and 5-free digraphs. Liang, Hao; Xu, Jun // Acta Mathematica Sinica;Jan2013, Vol. 29 Issue 1, p53 

    For a simple digraph G, let β( G) be the size of the smallest subset X ⊆ E( G) such that G−X has no directed cycles, and let γ( G) be the number of unordered pairs of nonadjacent vertices in G. A digraph G is called k-free if G has no directed cycles of length at most k. This...

  • On the Domination Number of Cartesian Product of Two Directed Cycles. Zehui Shao; Enqiang Zhu; Fangnian Lang // Journal of Applied Mathematics;2013, p1 

    Denote by ɣ(G) the domination number of a digraph G and CmCn the Cartesian product of Cm and Cn, the directed cycles of length m, n = 2. In 2010, Liu et al. determined the exact values of ɣ(CmCn) for m = 2, 3, 4, 5, 6. In 2013, Mollard determined the exact values of ɣ(CmCn)...

  • A CHARACTERIZATION OF LOCATING-TOTAL DOMINATION EDGE CRITICAL GRAPHS. BLIDIA, MOSTAFA; DALI, WIDAD // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 1, p197 

    No abstract available.

  • PAIRED DOMINATION IN PRISMS OF GRAPHS. MYNHARDT, CHRISTINA M.; SCHURCH, MARK // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 1, p5 

    No abstract available.

  • A NOTE ON PATH DOMINATION. ALCÓN, LILIANA // Discussiones Mathematicae: Graph Theory;2016, Vol. 36 Issue 4, p1021 

    We study domination between different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks). We succeeded in characterizing those graphs in which every uv-walk of one particular kind dominates every uv-walk of other specific...

  • Majority Domatic Number - I. Manora, J. Joseline; Swaminathan, V. // Global Journal of Pure & Applied Mathematics;2010, Vol. 6 Issue 3, p275 

    In any democratic set up, the party which has majority of seats is given the opportunity to rule the state. To model such instances, the concept majority domination is introduced. This chapter deals with partitioning the vertex set into as many disjoint subsets, each being a majority dominating...

  • GRAPHS WITH EQUAL DOMINATION AND 2-DISTANCE DOMINATION NUMBERS. RACZEK, JOANNA // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p375 

    No abstract available.

Share

Read the Article

Courtesy of NEW JERSEY STATE LIBRARY

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics