PANCHROMATIC PATTERNS BY PATHS
Por:
Benítez-Bobadilla G., Galeana-Sánchez H., Hernández-Cruz C.
Publicada:
1 ene 2024
Ahead of Print:
1 may 2022
Resumen:
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 absorbent by H-paths of D if every vertex in VD - S reaches some vertex in S by H-paths, and it is independent by H-paths if no vertex in S can reach another (different) vertex in S by H-paths. A kernel by H-paths is a subset of VD which is independent by H-paths and absorbent by H-paths. We define Be1 as the set of digraphs H such that any H-arc-coloured tournament has an absorbent by H-paths vertex; the set Be2 consists of the digraphs H such that any H-arc-coloured digraph D has an independent, absorbent by H-paths set; analogously, the set Be3 is the set of digraphs H such that every H-arc-coloured digraph D contains a kernel by H-paths. In this work, we point out similarities and differences between reachability by H-walks and reachability by H-paths. We present a characterization of the patterns H such that for every digraph D and every H-arc-colouring of D, every H-walk between two vertices in D contains an H-path with the same endpoints. We provide advances towards a characterization of the digraphs in Be3. In particular, we show that if a specific digraph is not in Be3, then the structure of the digraphs in the family is completely determined. © 2024 University of Zielona Gora. All rights reserved.
Filiaciones:
Benítez-Bobadilla G.:
Instituto de Matemáticas Universidad Nacional Autónoma de México, Ciudad de México, Mexico
Galeana-Sánchez H.:
Instituto de Matemáticas Universidad Nacional Autónoma de México, Ciudad de México, Mexico
Hernández-Cruz C.:
Facultad de Ciencias Universidad Nacional Autónoma de México, Ciudad de México, Mexico
gold, Green Submitted, All Open Access; Gold Open Access; Green Open Access
|