پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شماره‌ها | 1,676 |
| تعداد مقالات | 13,679 |
| تعداد مشاهده مقاله | 31,706,790 |
| تعداد دریافت فایل اصل مقاله | 12,527,409 |
$H$-Kernels by walks in subdivision digraph | ||
| Transactions on Combinatorics | ||
| مقاله 22، دوره 9، شماره 2، شهریور 2020، صفحه 61-75 اصل مقاله (272.29 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2020.107875.1529 | ||
| نویسندگان | ||
| Hortensia Galeana-Sánchez1؛ Roc´ıo Rojas-Monroy2؛ Rocio Sanchez Lopez* 3؛ Berta Zavala-Santana2 | ||
| 1Ciudad Universitaria,Coyoacán 04510,Ciudad de México, México | ||
| 2Universidad Autónoma del Estado de México, Estado de México | ||
| 3Department of Mathematics, Science Faculty, UNAM | ||
| چکیده | ||
| 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). A directed walk $W$ in $D$ is said to be an $H$-walk if and only if the consecutive colors encountered on $W$ form a directed walk in $H$. A subset $N$ of the vertices of $D$ is said to be an $H$-kernel by walks if (1) for every pair of different vertices in $N$ there is no $H$-walk between them ($N$ is $H$-independent by walks) and (2) for each vertex $u$ in $V$($D$)-$N$ there exists an $H$-walk from $u$ to $N$ in $D$ ($N$ is $H$-absorbent by walks). Suppose that $D$ is a digraph possibly infinite. In this paper we will work with the subdivision digraph $S_H$($D$) of $D$, where $S_H$($D$) is an $H$-colored digraph defined as follows: $V$($S_H$($D$)) = $V$($D$) $\cup$ $A$($D$) and $A$($S_H$($D$)) = \{($u$,$a$) : $a$ = ($u$,$v$) $\in$ $A$($D$)\} $\cup$ \{($a$,$v$) : $a$ = ($u$,$v$) $\in$ $A$($D$)\}, where ($u$, $a$, $v$) is an $H$-walk in $S_H$($D$) for every $a$ = ($u$,$v$) in $A$($D$). We will show sufficient conditions on $D$ and on $S_H$($D$) which guarantee the existence or uniqueness of $H$-kernels by walks in $S_H$($D$). | ||
| کلیدواژه‌ها | ||
| Kernel؛ Kernel by monochromatic paths؛ $H$-kernel by walks؛ subdivision digraph | ||
| مراجع | ||
|
[1] P. Arpin and V. Linek, Reachability problems in edge-colored digraphs, Discrete Math., 307 (2007) 2276–2289.
[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2000.
[3] C. Berge, Graphs, North-Holland, Amsterdan, 1989.
[4] E. Boros, V. Gurvich, Perfect graphs, kernels and cores of cooperative games, RUTCOR Research Report 12. Rutgers University, april 2003. [5] V. Chvátal, On the computational complexity of finding a kernel, Report CRM300, Centre de Recherches Mathématiques, Université de Montréal, 1973. [6] A. S. Fraenkel, Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction, Electron J. Combin., 14 (DS2) (2009). [7] H. Galeana-Sánchez and R. Rojas-Monroy, Kernels and some operations in edge-coloured digraphs, Discrete Math., 308 (2008) 6036–6046. [8] T. W. Haynes, S.T. Hedetniemi and P. J. Slater, Domination in graphs: advanced topics. Monographs and textbooks in pure and applied mathematics 209, Marcel Dekker Inc, New York, 1998. [9] T. W. Haynes, S.T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Chapman and Hall/CRC Pure and Applied Mathematics 464. Marcel Dekker Inc, New York, 1998. [10] V. Linek and B. Sands, A note on paths in edge-colored tournaments, Ars Combin., 44 (1996) 225–228.
[11] von J. Neumann and O. Morgenstern, Theory of games and economic behavior, Princeton University Press, Prince- ton, NJ, 1944. [12] R. Rojas-Monroy and J. I. Villarreal-Valdés, Kernels in infinite digraphs, AKCE J. Graphs. Combin., 7 no. 1 (2010) 103–111. [13] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge coloured digraphs, J. Combin. Theory Ser. B, 33 (1982) 271–275. [14] J. Topp, kernels of digraphs formed by some unary operations from other digraphs, J. Rostock Math. Kolloq., 21 (1982) 73–81. | ||
|
آمار تعداد مشاهده مقاله: 474 تعداد دریافت فایل اصل مقاله: 451 |
||