CKI-Digraphs, Generalized Sums and Partitions of Digraphs

详细信息    查看全文

• 作者：Hortensia Galeana-Sánchez ; Mika Olsen
• 关键词：Digraphs ; Kernel ; CKI ; digraphs ; Operations in digraphs ; 05C15 ; 05C20
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：32
• 期：1
• 页码：123-131
• 全文大小：431 KB
• 参考文献：1.Balbuena, C., Guevara, M., Olsen, M.: Structural properties of CKI-digraphs. AKCE Int. J. Graphs Comb. 11(1), 67–80 (2014)MATH MathSciNet
  2.Bang-Jensen, J., Gutin, G.: Digraphs: theory, algorithms and applications. Springer, London (2001)
  3.Berge, C.: Graphs. North-Holland, Amsterdam (1985)MATH
  4.Berge, C., Duchet, P.: Recent problems and results about kernels in directed graphs. Discrete Math. 86, 27–31 (1990)MATH MathSciNet CrossRef
  5.Boros, E., Gurvich, V.: Perfect graphs, kernels and cores of cooperative games. Discrete Math. 306, 2336–2354 (2006)MATH MathSciNet CrossRef
  6.Duchet, P.: Representation: noyaux en théorie des graphes et hypergraphes. Thèse, Paris (1979)
  7.Galeana-Sánchez, H.: A new characterization of perfect graphs. Discrete Math. 312, 2751–2755 (2012)MATH MathSciNet CrossRef
  8.Galeana-Sánchez, H., Neumann-Lara, V.: On Kernel-perfect critical digraphs. Discrete Math. 59, 257–265 (1986)
  9.Galeana-Sánchez, H., Neumann-Lara, V.: On the dichromatic number in Kernel theory. Mathematica Slovaca 48(3), 213–2219 (1998)MATH MathSciNet
  10.Galeana-Sánchez, H., Olsen, M.: Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3. Discrete Math. 313, 1464–1474 (2013)MATH MathSciNet CrossRef
  11.Haynes, T.W., Hedetniemi, T., Slater, P.J. (eds.): Domination in graphs, advanced topics. Marcel Dekker Inc. (1998)
  12.Neumann-Lara, V.: Seminúcleos de una digráfica. Anales del Instituto de Matemáticas UNAM II (1971)
  
• 作者单位：Hortensia Galeana-Sánchez (1)
  Mika Olsen (2)
  
  1. Instituto de Matemáticas, Universidad Nacional Autónoma de México, Circuito Exterior, Ciudad Universitaria, 04510, Mexico DF, México
  2. Departamento de Matemáticas Aplicadas y Sistemas, Universidad Autónoma Metropolitana-Cuajimalpa, Av Vasco de Quiroga 4871, 05348, Mexico DF, México
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

A kernel of a digraph is a set of vertices which is both independent and absorbent. Let \(D\) be a digraph such that every proper induced subdigraph of \(D\) has a kernel; \(D\) is said to be kernel perfect digraph (KP-digraph) if the digraph \(D\) has a kernel and critical kernel imperfect digraph (CKI-digraph) if the digraph \(D\) does not have a kernel. We characterize the CKI-digraphs with a partition into an independent set and a semicomplete digraph. The generalized sum \(G(F_u)\) of a family of mutually disjoint digraphs \(\{F_u\}_{u\in V(G)}\) over a graph \(G\) is a digraph defined as follows: Consider \(\cup _{u\in V(G)}F_u\), and for each \(x\in V(F_v)\) and \(y\in V(F_w)\) with \(\{v,w\}\in E(G)\) choose exactly one of the two arcs \((x,y)\) or \((y,x)\). We characterize the asymmetric CKI-digraphs which are generalized sums over an edge or a cycle. Furthermore, we give sufficient conditions on \(G\) and the family \(\{F_u\}_{u\in V(G)}\), such that the generalized sum \(G(F_u)\) has a kernel or is a is KP-digraph. Keywords Digraphs Kernel CKI-digraphs Operations in digraphs