TITLE

# Î³-CYCLES AND TRANSITIVITY BY MONOCHROMATIC PATHS IN ARC-COLOURED DIGRAPHS

AUTHOR(S)
CASAS-BAUTISTA, ENRIQUE; GALEANA-SÁNCHEZ, HORTENSIA; ROJAS-MONROY, ROCÍO
PUB. DATE
November 2013
SOURCE
Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 3, p493
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. If D is an m-coloured digraph and a âˆˆ A(D), colour(a) will denote the colour has been used on a. A path (or a cycle) is called monochromatic if all of its arcs are coloured alike. A Î³-cycle in D is a sequence of vertices, say Î³ = (u0, u1, ..., un), such that ui â‰  uj if i â‰  j and for every i âˆˆ {0, 1, ..., n} there is a uiui+1-monochromatic path in D and there is no ui+1ui-monochromatic path in D (the indices of the vertices will be taken mod n+1). 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 path between them and; (ii) for every vertex x âˆˆ V (D) \ N there is a vertex y âˆˆ N such that there is an xy-monochromatic path. Let D be a finite m-coloured digraph. Suppose that {C1,C2} is a partition of C, the set of colours of D, and Di will be the spanning subdigraph of D such that A(Di) = {a âˆˆ A(D) | colour(a) âˆˆ Ci}. In this paper, we give some sufficient conditions for the existence of a kernel by monochromatic paths in a digraph with the structure mentioned above. In particular we obtain an extension of the original result by B. Sands, N. Sauer and R. Woodrow that asserts: Every 2-coloured digraph has a kernel by monochromatic paths. Also, we extend other results obtained before where it is proved that under some conditions an m-coloured digraph has no Î³-cycles.
ACCESSION #
89421019

## Related Articles

• CHOICE-PERFECT GRAPHS. TUZA, ZSOLT // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 1, p231

Given a graph G = (V, E) and a set Lv of admissible colors for each vertex v âˆˆ V (termed the list at v), a list coloring of G is a (proper) vertex coloring Ï† : V â†’ â‹ƒvâˆˆV Lv such that Ï†(v) âˆˆ Lv for all v âˆˆ V and Ï†(u) â‰  Ï†(v) for all uv âˆˆ...

• A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture. Leidner, Maxfield // Graphs & Combinatorics;Mar2014, Vol. 30 Issue 2, p377

The article shrinks the Î” = 6 hole that exists in the family of planar graphs which satisfy the total coloring conjecture. Let G be a planar graph. If $${v_n^k}$$ represents the number of vertices of degree n which lie on k distinct 3-cycles, for $${n, k \in \mathbb{N}}$$ , then the...

• An Algorithm to Detect Cycle in an Undirected Graph. Kumar, Anand; Jani, N. N. // International Journal of Computational Intelligence Research;2010, Vol. 6 Issue 2, p305

This paper presents a novel algorithm to detect cycles in a graph. The graph may be of any type. Cycles are available in a graph and in much real life application; it is required to know the existence of cycles in a graph. This algorithm is developed in the context of network design problem but...

• 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 MONOCHROMATIC PATHS AND BICOLORED SUBDIGRAPHS IN ARC-COLORED TOURNAMENTS. DELGADO-ESCALANTE, PIETRA; GALEANA-SANCHEZ, HORTENSIA // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 4, p791

Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n âˆˆ N such that there is a monochromatic directed path from v to n....

• $$\varPi$$ -Kernels in Digraphs. Galeana-Sánchez, Hortensia; Montellano-Ballesteros, Juan // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2207

Let $$D=(V(D), A(D))$$ be a digraph, $$DP(D)$$ be the set of directed paths of $$D$$ and let $$\varPi$$ be a subset of $$DP(D)$$ . A subset $$S\subseteq V(D)$$ will be called $$\varPi$$ -independent if for any pair $$\{x, y\} \subseteq S$$ , there is no $$xy$$ -path nor $$yx$$ -path in...

• On Arc Connectivity of Direct-Product Digraphs. Tiedan Zhu; Jianping Ou // Journal of Applied Mathematics;2012, p1

Four natural orientations of the direct product of two digraphs are introduced in this paper. Sufficient and necessary conditions for these orientations to be strongly connected are presented, as well as an explicit expression of the arc connectivity of a class of direct-product digraphs.

• A Toughness Condition for a Spanning Tree With Bounded Total Excesses. Ozeki, Kenta // Graphs & Combinatorics;Sep2015, Vol. 31 Issue 5, p1679

Let $$k$$ be an integer with $$k \ge 2$$ . In terms of the toughness of a graph, Win gave a sufficient condition for the existence of a spanning $$k$$ -tree, that is, a spanning tree in which the maximum degree is at most $$k$$ . For a spanning tree $$T$$ of a graph $$G$$ , we define the total...

• The Existence of an Alternating Sign on a Spanning Tree of Graphs. KIM, DONGSEOK; KWON, YOUNG SOO; LEE, JAEUN // Kyungpook Mathematical Journal;Dec2012, Vol. 52 Issue 4, p513

For a spanning tree T of a connected graph .. and for a labelling Î¦: E(T ) ! {+,-}, Î¦ is called an alternating sign on a spanning tree T of a graph ... if for any cotree edge e âˆˆ E(...)-E(T ), the unique path in T joining both end vertices of e has alternating signs. In the present...

Share