ArticleOriginal scientific text

Title

Kernels in edge coloured line digraph

Authors 1, 2

Affiliations

  1. Instituto de Matemáticas, U.N.A.M., C.U., Circuito Exterior, D. F. 04510 México
  2. Departamento de Matemáticas de la Facultad de Ciencias de la Universidad Nacional Autónoma de México, México, D.F.

Abstract

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions (i) for every pair of different vertices u, v ∈ N there is no monochromatic directed 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 directed path. Let D be an m-coloured digraph and L(D) its line digraph. The inner m-coloration of L(D) is the edge coloration of L(D) defined as follows: If h is an arc of D of colour c, then any arc of the form (x,h) in L(D) also has colour c. In this paper it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner edge coloration of L(D).

Keywords

kernel, kernel by monochromatic paths, line digraph, edge coloured digraph

Bibliography

  1. C. Berge, Graphs (North Holland, Amsterdam, New York, 1985).
  2. H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V.
  3. H. Galeana-Sánchez and J.J. García Ruvalcaba, Kernels in {C₃, T₃}-free arc colorations of Kₙ - e, submitted.
  4. B. Sands, N. Sauer and R. Woodrow, On Monochromatic Paths in Edge Coloured Digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8.
  5. Shen Minggang, On Monochromatic Paths in m-Coloured Tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7.
Pages:
91-98
Main language of publication
English
Received
1997-04-27
Accepted
1997-09-22
Published
1998
Exact and natural sciences