Discussiones Mathematicae
Graph Theory 18(1) (1998) 91-98
DOI: https://doi.org/10.7151/dmgt.1066
KERNELS IN EDGE COLOURED LINE DIGRAPH
H. Galeana-Sánchez Instituto de Matemáticas, U.N.A.M., C.U. |
L. Pastrana Ramírez Departamento de Matemáticas de la Facultad de
Ciencias |
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.
1991 Mathematics Subject Classification: 05C20.
References
| [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 { C3, T3}-free arc colorations of Kn-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. |
Received 27 April 1997
Revised 22 September 1997
Close