The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Nonderogatory unicyclic digraphs.”

Independent Detour Transversals in 3-Deficient Digraphs

Susan van Aardt, Marietjie Frick, Joy Singleton (2013)

Discussiones Mathematicae Graph Theory

Similarity:

In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph...

On a conjecture of quintas and arc-traceability in upset tournaments

Arthur H. Busch, Michael S. Jacobson, K. Brooks Reid (2005)

Discussiones Mathematicae Graph Theory

Similarity:

A digraph D = (V,A) is arc-traceable if for each arc xy in A, xy lies on a directed path containing all the vertices of V, i.e., hamiltonian path. We prove a conjecture of Quintas [7]: if D is arc-traceable, then the condensation of D is a directed path. We show that the converse of this conjecture is false by providing an example of an upset tournament which is not arc-traceable. We then give a characterization for upset tournaments in terms of their score sequences, characterize which...

Isomorphisms and traversability of directed path graphs

Hajo Broersma, Xueliang Li (2002)

Discussiones Mathematicae Graph Theory

Similarity:

The concept of a line digraph is generalized to that of a directed path graph. The directed path graph Pₖ(D) of a digraph D is obtained by representing the directed paths on k vertices of D by vertices. Two vertices are joined by an arc whenever the corresponding directed paths in D form a directed path on k+1 vertices or form a directed cycle on k vertices in D. In this introductory paper several properties of P₃(D) are studied, in particular with respect to isomorphism and traversability....

Exponents of two-colored digraphs

Yan Ling Shao, Yubin Gao (2009)

Czechoslovak Mathematical Journal

Similarity:

We consider the primitive two-colored digraphs whose uncolored digraph has n + s vertices and consists of one n -cycle and one ( n - 3 ) -cycle. We give bounds on the exponents and characterizations of extremal two-colored digraphs.

Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs

Hortensia Galeana-Sánchez, R. Rojas-Monroy, B. Zavala (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured...

Kernels in monochromatic path digraphs

Hortensia Galeana-Sánchez, Laura Pastrana Ramírez, Hugo Alberto Rincón Mejía (2005)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. Let D be an m-coloured digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them and (ii) for each vertex x ∈...