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

Abstract

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

How to cite

top

H. 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. [1] C. Berge, Graphs (North Holland, Amsterdam, New York, 1985). 
  2. [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. [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. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.