2019/03/24 by Benítez-Bobadilla, Germán, Galeana-Sánchez, Hortensia, Hernández-Cruz, César
#05C20 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.10031
Let H=(VH,AH) be a digraph, possibly with loops, and let D=(VD, AD) be a loopless multidigraph with a colouring of its arcs c: AD → VH. An H-path of D is a path (v0, …, vn) of D such that (c(vi-1, vi), c(vi,vi+1)) is an arc of H for every 1 ≤ i ≤ n-1. For u, v ∈ VD, we say that u reaches v by H-paths if there exists an H-path from u to v in D. A subset S ⊆ VD is H-absorbent of D if every vertex in VD-S reaches by H-paths some vertex in S, and it is H-independent if no vertex in S can reach another (different) vertex in S by H-pahts. An H-kernel is an independent by H-paths and absorbent by H-paths subset of VD. We define \mathscrB1 as the set of digraphs H such that any H-arc-coloured tournament has an H-absorbent by paths vertex; the set \mathscrB2 consists of the digraphs H such that any H-arc-coloured digraph D has an independent, H-absorbent by paths set; analogously, the set \mathscrB3 is the set of digraphs H such that every H-arc-coloured digraph D contains an H-kernel by paths. In this work, we present a characterization of \mathscrB2, and provide structural properties of the digraphs in \mathscrB3 which settle up its characterization except for the analysis of a single digraph on three vertices.