DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(3) (2013) 493-507
DOI: https://doi.org/10.7151/dmgt.1695

γ-cycles and transitivity by monochromatic paths in arc-coloured digraphs

Enrique Casas-Bautista(1)
Hortensia Galeana-Sánchez(2)
and
Rocío Rojas-Monroy(1)

(1) Facultad de Ciencias, Universidad Autónoma del Estado de México
Instituto Literario No. 100, Centro, 50000
Toluca, Edo. de México, México
(2) Instituto de Matemáticas
Universidad Nacional Autónoma de México
Ciudad Universitaria, México, D.F. 04510, México
e-mail: ecasasb@uaemex.mx, hgaleana@matem.unam.mx mrrm@uaemex.mx

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.

Keywords: digraph, kernel, kernel by monochromatic paths, γ-cycle

2010 Mathematics Subject Classification: 05C20, 05C38, 05C69.

References

[1]J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2001).
[2]C. Berge, Graphs (North-Holland, Amsterdam, 1985).
[3]C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27--31, doi: 10.1016/0012-365X(90)90346-J.
[4]P. Delgado-Escalante and H. Galena-Sánchez, Kernels and cycles' subdivisions in arc-colored tournaments, Discuss. Math. Graph Theory 29 (2009) 101--117, doi: 10.7151/dmgt.1435.
[5]P. Delgado-Escalante and H. Galena-Sánchez, On monochromatic paths and bicolored subdigraphs in arc-colored tournaments, Discuss. Math. Graph Theory 31 (2011) 791--820, doi: 10.7151/dmgt.1580.
[6]P. Duchet, Graphes noyau - parfaits, Ann. Discrete Math. 9 (1980) 93--101, doi: 10.1016/S0167-5060(08)70041-4.
[7]P. Duchet, Classical perfect graphs, An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 21 (1984) 67--96.
[8]P. Duchet and H. Meynel, A note on kernel-critical graphs, Discrete Math. 33 (1981) 103--105, doi: 10.1016/0012-365X(81)90264-8.
[9]H. Galena-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.
[10]H. Galena-Sánchez, Kernels in edge-coloured digraphs, Discrete Math. 184 (1998) 87--99, doi: 10.1016/S0012-365X(97)00162-3.
[11]H. Galena-Sánchez and J.J. García-Ruvalcaba, Kernels in the closure of coloured digraphs, Discuss. Math. Graph Theory 20 (2000) 243--254, doi: 10.7151/dmgt.1123.
[12]H. Galeana-Sánchez, J.J. García-Ruvalcaba, On graphs all of whose {C3,T3}-free arc colorations are kernel perfect, Discuss. Math. Graph Theory 21 (2001) 77--93, doi: 10.7151/dmgt.1134.
[13]H. Galena-Sánchez, G. Gaytán-Gómez and R. Rojas-Monroy, Monochromatic cycles and monochromatic paths in arc-coloured digraphs, Discuss. Math. Graph Theory 31 (2011) 283--292, doi: 10.7151/dmgt.1545.
[14]H. Galena-Sánchez, V. Neumann-Lara, On kernels and semikernels of digraphs, Discrete Math. 48 (1984) 67--76, doi: 10.1016/0012-365X(84)90131-6.
[15]H. Galeana-Sánchez, V. Neumann-Lara, On kernel-perfect critical digraphs, Discrete Math. 59 (1986) 257--265, doi: 10.1016/0012-365X(86)90172-X.
[16]H. Galeana-Sánchez and R. Rojas-Monroy, A counterexample to a conjecture on edge-coloured tournaments, Discrete Math. 282 (2004) 275--276, doi: 10.1016/j.disc.2003.11.015.
[17]H. Galeana-Sánchez and R. Rojas-Monroy, On monochromatic paths and monochromatic 4-cycles in edge coloured bipartite tournaments, Discrete Math. 285 (2004) 313--318, doi: 10.1016/j.disc.2004.03.005.
[18]H. Galeana-Sánchez, R. Rojas-Monroy, Independent domination by monochromatic paths in arc coloured bipartite tournaments, AKCE J. Graphs. Combin. 6 (2009) 267--285.
[19]H. Galeana-Sánchez and R. Rojas-Monroy, Monochromatic paths and monochromatic cycles in edge-coloured k-partite tournaments, Ars Combin. 97A (2010) 351--365.
[20]H. Galena-Sánchez, R. Rojas-Monroy and B. Zavala, Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs, Discuss. Math. Graph Theory 29 (2009) 337--347, doi: 10.7151/dmgt.1450.
[21]H. Galena-Sánchez, R. Rojas-Monroy and B. Zavala, Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs, Discuss. Math. Graph Theory 30 (2010) 545--553, doi: 10.7151/dmgt.1512.
[22]G. Hahn, P. Ille and R. Woodrow, Absorbing sets in arc-coloured tournaments, Discrete Math. 283 (2004) 93--99, doi: 10.1016/j.disc.2003.10.024.
[23]J.M. Le Bars, Counterexample of the 0-1 law for fragments of existential second-order logic; an overview, Bull. Symbolic Logic 6 (2000) 67--82, doi: 10.2307/421076.
[24]J.M. Le Bars, The 0-1 law fails for frame satisfiability of propositional model logic, in: Proceedings of the 17th Symposium on Logic in Computer Science (2002) 225--234, doi: 10.1109/LICS.2002.1029831.
[25]J. von Leeuwen, Having a Grundy numbering is NP-complete, Report 207 Computer Science Department, Pennsylvania State University, University Park, PA (1976).
[26]J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton University Press, Princeton, 1944).
[27]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.
[28]S. Minggang, On monochromatic paths in m-coloured tournaments, J. Combin, Theory (B) 45 (1988) 108--111, doi: 10.1016/0095-8956(88)90059-7.
[29]I. Włoch, On kernels by monochromatic paths in the corona of digraphs, Cent. Eur. J. Math. 6 (2008) 537--542, doi: 10.2478/s11533-008-0044-6.
[30]I. Włoch, On imp-sets and kernels by monochromatic paths in duplication, Ars Combin. 83 (2007) 93--99.

Received 31 January 2012
Revised 15 April 2013
Accepted 15 April 2013

Close