(A, ℬ)-kernels and Sands, Sauer and Woodrow’s theorem
Let D = (V(D), A(D)) a digraph. Consider the set PD= {P : P is a non trivial finite directed path in D} and let A and ℬ two subsets of PD. A subset N of V(D) is said to be an (A, ℬ)-kernel of D if (1) for every subset {u, v} of N there exists no uv-directed path P such that P∈A(N is A-independent) a...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2019-12-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S0972860017301366 |
| _version_ | 1818328470261858304 |
|---|---|
| author | Hortensia Galeana-Sánchez Rocío Rojas-Monroy Rocío Sánchez-López |
| author_facet | Hortensia Galeana-Sánchez Rocío Rojas-Monroy Rocío Sánchez-López |
| author_sort | Hortensia Galeana-Sánchez |
| collection | DOAJ |
| description | Let D = (V(D), A(D)) a digraph. Consider the set PD= {P : P is a non trivial finite directed path in D} and let A and ℬ two subsets of PD. A subset N of V(D) is said to be an (A, ℬ)-kernel of D if (1) for every subset {u, v} of N there exists no uv-directed path P such that P∈A(N is A-independent) and (2) for every vertex x in V(D)∖N there exist y in N and P in ℬ such that P is an xy-directed path (N is ℬ-absorbent). In particular, this is a generalization of the concept kernel by monochromatic directed paths in an m-colored digraph when A=ℬ = {P∈PD: P is a monochromatic directed path}. A classical result in kernel theory establishes that if D is a 2-colored digraph without monochromatic infinite outward paths, then D has a kernel by monochromatic directed paths; this result is known as Sands, Sauer and Woodrow’s theorem. In this paper we show an extension of this result in the context of (A, ℬ)-kernels, for possibly infinite digraphs, as follows: Let D be a digraph, possible infinite, and A and ℬ two subsets of PDsuch that (A, ℬ)P. Suppose that (1) {V1, V2} is a partition of A such that Viis Vi-transitive for each i in {1, 2}, (2) for i in {1, 2}, if (xn)n∈Nis a Vi-infinite outward path, then there exists j in N such that there exists a directed path from xj+1to xjin Vi. Then D has an (A, ℬ)-kernel. Generalizations of many previous results are obtained as a direct consequence of this theorem. Keywords: Kernel, Kernel by monochromatic paths, (k, l)-kernel, H-colored digraph, H-kernel |
| first_indexed | 2024-12-13T12:32:40Z |
| format | Article |
| id | doaj.art-e1858789ad04480b80e51a044b6fbd28 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 |
| language | English |
| last_indexed | 2024-12-13T12:32:40Z |
| publishDate | 2019-12-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-e1858789ad04480b80e51a044b6fbd282022-12-21T23:45:59ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002019-12-01163284290(A, ℬ)-kernels and Sands, Sauer and Woodrow’s theoremHortensia Galeana-Sánchez0Rocío Rojas-Monroy1Rocío Sánchez-López2Instituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la Investigación Científica, Circuito Exterior, Ciudad Universitaria, Coyoacán 04510, Ciudad de México, MexicoFacultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario No. 100, Centro, 50000, Toluca, Edo. de México, MexicoFacultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad Universitaria, Coyoacán 04510, Ciudad de México, Mexico; Facultad de Ciencias, Universidad Autónoma del Estado de México, Instituto Literario No. 100, Centro, 50000, Toluca, Edo. de México, Mexico; Corresponding author at: Facultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad Universitaria, Coyoacán 04510, Ciudad de México, México.Let D = (V(D), A(D)) a digraph. Consider the set PD= {P : P is a non trivial finite directed path in D} and let A and ℬ two subsets of PD. A subset N of V(D) is said to be an (A, ℬ)-kernel of D if (1) for every subset {u, v} of N there exists no uv-directed path P such that P∈A(N is A-independent) and (2) for every vertex x in V(D)∖N there exist y in N and P in ℬ such that P is an xy-directed path (N is ℬ-absorbent). In particular, this is a generalization of the concept kernel by monochromatic directed paths in an m-colored digraph when A=ℬ = {P∈PD: P is a monochromatic directed path}. A classical result in kernel theory establishes that if D is a 2-colored digraph without monochromatic infinite outward paths, then D has a kernel by monochromatic directed paths; this result is known as Sands, Sauer and Woodrow’s theorem. In this paper we show an extension of this result in the context of (A, ℬ)-kernels, for possibly infinite digraphs, as follows: Let D be a digraph, possible infinite, and A and ℬ two subsets of PDsuch that (A, ℬ)P. Suppose that (1) {V1, V2} is a partition of A such that Viis Vi-transitive for each i in {1, 2}, (2) for i in {1, 2}, if (xn)n∈Nis a Vi-infinite outward path, then there exists j in N such that there exists a directed path from xj+1to xjin Vi. Then D has an (A, ℬ)-kernel. Generalizations of many previous results are obtained as a direct consequence of this theorem. Keywords: Kernel, Kernel by monochromatic paths, (k, l)-kernel, H-colored digraph, H-kernelhttp://www.sciencedirect.com/science/article/pii/S0972860017301366 |
| spellingShingle | Hortensia Galeana-Sánchez Rocío Rojas-Monroy Rocío Sánchez-López (A, ℬ)-kernels and Sands, Sauer and Woodrow’s theorem AKCE International Journal of Graphs and Combinatorics |
| title | (A, ℬ)-kernels and Sands, Sauer and Woodrow’s theorem |
| title_full | (A, ℬ)-kernels and Sands, Sauer and Woodrow’s theorem |
| title_fullStr | (A, ℬ)-kernels and Sands, Sauer and Woodrow’s theorem |
| title_full_unstemmed | (A, ℬ)-kernels and Sands, Sauer and Woodrow’s theorem |
| title_short | (A, ℬ)-kernels and Sands, Sauer and Woodrow’s theorem |
| title_sort | a b kernels and sands sauer and woodrow s theorem |
| url | http://www.sciencedirect.com/science/article/pii/S0972860017301366 |
| work_keys_str_mv | AT hortensiagaleanasanchez abkernelsandsandssauerandwoodrowstheorem AT rociorojasmonroy abkernelsandsandssauerandwoodrowstheorem AT rociosanchezlopez abkernelsandsandssauerandwoodrowstheorem |