H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs
Let H be a digraph (possibly with loops) and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). For an arc (x, y) of D, its color is denoted by c(x, y). A directed path W = (v0, . . ., vn) in an H-colored digraph D will be called H-path if...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2021-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2199 |
| _version_ | 1797757748050395136 |
|---|---|
| author | Campero-Alonzo José Manuel Sánchez-López Rocío |
| author_facet | Campero-Alonzo José Manuel Sánchez-López Rocío |
| author_sort | Campero-Alonzo José Manuel |
| collection | DOAJ |
| description | Let H be a digraph (possibly with loops) and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). For an arc (x, y) of D, its color is denoted by c(x, y). A directed path W = (v0, . . ., vn) in an H-colored digraph D will be called H-path if and only if (c(v0, v1), . . ., c(vn−1, vn)) is a directed walk in H. In W, we will say that there is an obstruction on viif (c(vi−1, vi), c(vi, vi+1)) /∉ A(H) (if v0 = vnwe will take indices modulo n). A subset N of V (D) is said to be an H-kernel in D if for every pair of di erent vertices in N there is no H-path between them, and for every vertex u in V (D) \ N there exists an H-path in D from u to N. Let D be an arc-colored digraph. The color-class digraph of D, 𝒞C(D), is the digraph such that V (𝒞C(D)) = {c(a) : a ∈ A(D)} and (i, j) ∈ A(𝒞C(D)) if and only if there exist two arcs, namely (u, v) and (v, w) in D, such that c(u, v) = i and c(v, w) = j. The main result establishes that if D = D1 ∪ D2 is an H-colored digraph which is a union of asymmetric quasi-transitive digraphs and {V1, . . ., Vk} is a partition of V (𝒞C(D)) with a property P* such that |
| first_indexed | 2024-03-12T18:20:01Z |
| format | Article |
| id | doaj.art-4d6138b82e5342cfacfd911940c59311 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:20:01Z |
| publishDate | 2021-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-4d6138b82e5342cfacfd911940c593112023-08-02T08:58:21ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922021-05-0141239140810.7151/dmgt.2199H-Kernels in Unions of H-Colored Quasi-Transitive DigraphsCampero-Alonzo José Manuel0Sánchez-López Rocío1Facultad de Ciencias Universidad Nacional Autónoma de MéxicoCírcuito Exterior s/n, Coyoacán Ciudad Universitaria, 04510, Ciudad de México, CDMXFacultad de Ciencias Universidad Nacional Autónoma de MéxicoCírcuito Exterior s/n, Coyoacán Ciudad Universitaria, 04510, Ciudad de México, CDMXLet H be a digraph (possibly with loops) and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). For an arc (x, y) of D, its color is denoted by c(x, y). A directed path W = (v0, . . ., vn) in an H-colored digraph D will be called H-path if and only if (c(v0, v1), . . ., c(vn−1, vn)) is a directed walk in H. In W, we will say that there is an obstruction on viif (c(vi−1, vi), c(vi, vi+1)) /∉ A(H) (if v0 = vnwe will take indices modulo n). A subset N of V (D) is said to be an H-kernel in D if for every pair of di erent vertices in N there is no H-path between them, and for every vertex u in V (D) \ N there exists an H-path in D from u to N. Let D be an arc-colored digraph. The color-class digraph of D, 𝒞C(D), is the digraph such that V (𝒞C(D)) = {c(a) : a ∈ A(D)} and (i, j) ∈ A(𝒞C(D)) if and only if there exist two arcs, namely (u, v) and (v, w) in D, such that c(u, v) = i and c(v, w) = j. The main result establishes that if D = D1 ∪ D2 is an H-colored digraph which is a union of asymmetric quasi-transitive digraphs and {V1, . . ., Vk} is a partition of V (𝒞C(D)) with a property P* such thathttps://doi.org/10.7151/dmgt.2199quasi-transitive digraphkernel by monochromatic pathsalternating kernelh-kernelobstruction05c2005c3805c69 |
| spellingShingle | Campero-Alonzo José Manuel Sánchez-López Rocío H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs Discussiones Mathematicae Graph Theory quasi-transitive digraph kernel by monochromatic paths alternating kernel h-kernel obstruction 05c20 05c38 05c69 |
| title | H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs |
| title_full | H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs |
| title_fullStr | H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs |
| title_full_unstemmed | H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs |
| title_short | H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs |
| title_sort | h kernels in unions of h colored quasi transitive digraphs |
| topic | quasi-transitive digraph kernel by monochromatic paths alternating kernel h-kernel obstruction 05c20 05c38 05c69 |
| url | https://doi.org/10.7151/dmgt.2199 |
| work_keys_str_mv | AT camperoalonzojosemanuel hkernelsinunionsofhcoloredquasitransitivedigraphs AT sanchezlopezrocio hkernelsinunionsofhcoloredquasitransitivedigraphs |