<p>In this paper, we introduce a generalization of a kernel for vertex-colored digraphs. Let <i>D</i> be a digraph, we say that a function <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(c:V(D)\rightarrow \{0,1,\ldots \}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>:</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo stretchy="false">→</mo> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> is a <i>c</i>-coloring of <i>D</i>. An up-color kernel of <i>D</i>, <i>K</i>, is a set of vertices that holds: i)for every vertex <i>v</i> in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(V(D)\setminus K\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mi>K</mi> </mrow> </math></EquationSource> </InlineEquation>, there exists a vertex <i>w</i> in <i>K</i>, which is adjacent to <i>v</i> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(c(v)&lt;c(w)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mi>c</mi> <mo stretchy="false">(</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, ii)<i>K</i> does not contain any vertex having color 0, and iii)every pair of vertices in <i>K</i> is not adjacent, that is, <i>K</i> is an independent set. We give sufficient and necessary conditions for some families of digraphs (directed paths, directed cycles, forests, wheels, digraphs which have a unique cycle, cycles with chords), as well as for certain products of digraphs (the Cartesian and strong products, the Zykov sum, the generalization of crown and the line digraph), to have an up-color kernel.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Kernels in digraphs with colored vertices

  • Mucuy-kak Guevara,
  • Teresa I. Hoekstra-Mendoza,
  • Miguel Licona

摘要

In this paper, we introduce a generalization of a kernel for vertex-colored digraphs. Let D be a digraph, we say that a function \(c:V(D)\rightarrow \{0,1,\ldots \}\) c : V ( D ) { 0 , 1 , } is a c-coloring of D. An up-color kernel of D, K, is a set of vertices that holds: i)for every vertex v in \(V(D)\setminus K\) V ( D ) \ K , there exists a vertex w in K, which is adjacent to v and \(c(v)<c(w)\) c ( v ) < c ( w ) , ii)K does not contain any vertex having color 0, and iii)every pair of vertices in K is not adjacent, that is, K is an independent set. We give sufficient and necessary conditions for some families of digraphs (directed paths, directed cycles, forests, wheels, digraphs which have a unique cycle, cycles with chords), as well as for certain products of digraphs (the Cartesian and strong products, the Zykov sum, the generalization of crown and the line digraph), to have an up-color kernel.