Richardson's Theorem in H-coloured Digraphs

详细信息    查看全文

• 作者：Hortensia Galeana-Sánchez ; Rocío Sánchez-López
• 关键词：Kernel ; Kernel by monochromatic paths ; Color ; class digraph ; H ; coloured digraph ; H ; kernel
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：32
• 期：2
• 页码：629-638
• 全文大小：403 KB
• 参考文献：1.Arpin, P., Linek, V.: Reachability problems in edge-colored digraphs. Discrete. Math. 307, 2276–2289 (2007)CrossRef MathSciNet MATH
  2.Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications. Springer, London (2000)
  3.Berge, C.: Graphs. North-Holland, Amsterdan (1989)
  4.Boros, E., Gurvich, V.: Perfect graphs, kernels and cores of cooperative games. RUTCOR Research Report 12. Rutgers University (2003)
  5.Chvátal, V.: On the computational complexity of finding a kernel, report CRM300. Université de Montréal, Centre de Recherches Mathématiques (1973)
  6.Delgado-Escalante, P., Galeana-Sánchez, H.: Restricted domination in arc-colored digraphs. AKCE Int. J. Comb. 1, 95–104 (2014)
  7.Fraenkel, A.S.: Planar Kernel and Grundy with d\(\le 3, \text{ d }_{out}\le 2\) , \(\text{ d }_{in} \le 2\) , are NP-complete. Discrete. Appl. Math. 3, 257–262 (1981)CrossRef MathSciNet MATH
  8.Fraenkel, A.S.: Combinatorial games: selected bibliography with a succinct gourmet introduction. Electron. J. Combin. 14(DS2) (2009) http://​www.​combinatorics.​org/​ojs/​index.​php/​eljc/​article/​view/​ds2/​pdf
  9.Galeana-Sánchez, H.: Kernels in edge coloured digraphs. Discrete. Math. 184, 87–99 (1998)CrossRef MathSciNet MATH
  10.Galeana-Sánchez, H.: Kernels by monochromatic paths and the color-class digraph. Discuss. Math. Graph Theory 31, 273–281 (2011)CrossRef MathSciNet MATH
  11.Galeana-Sánchez, H., Sánchez-López, R.: H-kernels in infinite digraphs. Graphs Comb. 29(4), 913–920 (2013)CrossRef MATH
  12.Linek, V., Sands, B.: A note on paths in edge-colored tournaments. Ars Combin. 44, 225–228 (1996)MathSciNet MATH
  13.Neumann, J.V., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1944)MATH
  14.Neumann-Lara, V.: Seminúcleos de una digráfica. Ann. Inst. Math. 11, 55–62 (1971)MathSciNet
  15.Reid, K.B.: Monotone reachability in arc-colored tournaments. Congr. Numer. 146, 131–141 (2000)MathSciNet MATH
  16.Richardson, M.: Solutions of irreflexive relations. Ann. Math. 58(2), 573 (1953)CrossRef MATH
  17.Sands, B., Sauer, N., Woodrow, R.: On monochromatic paths in edge coloured digraphs. J. Combin. Theory Ser. B 33, 271–275 (1982)CrossRef MathSciNet MATH
  
• 作者单位：Hortensia Galeana-Sánchez (1)
  Rocío Sánchez-López (1)
  
  1. Instituto de Matemáticas UNAM, Ciudad Universitaria, Circuito Exterior, 04510, México, D.F., México
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

Let H be a digraph possibly with loops and D a finite digraph without loops whose arcs are coloured with the vertices of H (D is an H-coloured digraph). The sets V(D) and A(D) will denote the sets of vertices and arcs of D respectively. A directed path W in D is an H-path if and only if the consecutive colors encountered on W form a directed walk in H. A set \(N\subseteq \hbox {V}(D)\) is an H-kernel if for every pair of different vertices in N there is no H-path between them, and for every vertex \(u\in \hbox {V}(D){\setminus }N\) there exists an H-path in D from u to N. Let D be an m-coloured digraph. The color-class digraph of D, denoted by \({\mathscr {C}}_C(D\)), is the digraph such that: the vertices of the color-class digraph are the colors represented in the arcs of D, and \((i,j) \in A({\mathscr {C}}_C(D\))) if and only if there exist two arcs namely (u, v) and (v, w) in D such that (u, v) has color i and (v, w) has color j. Let \(W=(v_0, \ldots , v_n\)) be a directed walk in \({\mathscr {C}}_C(D)\), with D an H-coloured digraph, and \(e_i = (v_{i},v_{i+1})\) for each \(i \in \{0, \ldots ,n-1\}\). Let \(I = \{i_1, \ldots , i_k\}\) a subset of \(\{0, \ldots , n-1\}\) such that for 0 \(\le s \le n-1\), \(e_s \in \hbox { A}(H^c)\) if and only if \(s \in I\) (where \(H^c\) is the complement of H), then we will say that k is the \(H^c\)-length of W. Since V(\({\mathscr {C}}_C(D)) \subseteq \hbox {V}(H)\), the main question is: What structural properties of \({\mathscr {C}}_C(D)\), with respect to H, imply that D has an H-kernel? In this paper we will prove the following: If \({\mathscr {C}}_C(D)\) does not have directed cycles of odd \(H^c\)-length, then D has an H-kernel. Finally we will prove Richardson’s theorem as a direct consequence of the previous result.