# Kernels in edge coloured line digraph

H. Galeana-Sánchez; L. Pastrana Ramírez

Discussiones Mathematicae Graph Theory (1998)

- Volume: 18, Issue: 1, page 91-98
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topH. Galeana-Sánchez, and L. Pastrana Ramírez. "Kernels in edge coloured line digraph." Discussiones Mathematicae Graph Theory 18.1 (1998): 91-98. <http://eudml.org/doc/270565>.

@article{H1998,

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).
},

author = {H. Galeana-Sánchez, L. Pastrana Ramírez},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {kernel; kernel by monochromatic paths; line digraph; edge coloured digraph; digraph; monochromatic paths; edge colouration; line graph},

language = {eng},

number = {1},

pages = {91-98},

title = {Kernels in edge coloured line digraph},

url = {http://eudml.org/doc/270565},

volume = {18},

year = {1998},

}

TY - JOUR

AU - H. Galeana-Sánchez

AU - L. Pastrana Ramírez

TI - Kernels in edge coloured line digraph

JO - Discussiones Mathematicae Graph Theory

PY - 1998

VL - 18

IS - 1

SP - 91

EP - 98

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

LA - eng

KW - kernel; kernel by monochromatic paths; line digraph; edge coloured digraph; digraph; monochromatic paths; edge colouration; line graph

UR - http://eudml.org/doc/270565

ER -

## References

top- [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. Zbl0857.05054
- [3] H. Galeana-Sánchez and J.J. García Ruvalcaba, Kernels in {C₃, T₃}-free arc colorations of Kₙ - e, submitted. Zbl0990.05060
- [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. Zbl0488.05036
- [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. Zbl0654.05033

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.