<p>Given a digraph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_711_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="137" /> </InlineMediaObject> <EquationSource Format="TEX">\(D=(V(D),A(D))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, a set <i>S</i> of vertices of <i>D</i> is a <i>kernel</i> of <i>D</i> if it satisfies that: (i) for <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_711_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="62" /> </InlineMediaObject> <EquationSource Format="TEX">\( u,v\in S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>∈</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_711_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="100" /> </InlineMediaObject> <EquationSource Format="TEX">\( (u,v) \notin A(D)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>∉</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and (ii) for every <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_711_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="102" /> </InlineMediaObject> <EquationSource Format="TEX">\(u \in V(D)\setminus S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>∈</mo> <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>S</mi> </mrow> </math></EquationSource> </InlineEquation>, there exists <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_711_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(v \in S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation>, such that <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40590_2025_711_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="100" /> </InlineMediaObject> <EquationSource Format="TEX">\((u,v) \in A(D)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>∈</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. One of the most important results about kernels in digraphs is the following one, due to M.&#xa0;Richardson: Every digraph with no odd cycles has a kernel. The work and history of Graph Theory in Mexico is deeply woven with the study of kernels in digraphs and, particularly, with the work on Richardson’s theorem along with several generalizations of this result. In this paper, we provide a thorough review of this result and its generalizations.</p>

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

The theorem of Richardson and its generalizations: a survey

  • Ilan Goldfeder,
  • Miguel Tecpa-Galván

摘要

Given a digraph \(D=(V(D),A(D))\) D = ( V ( D ) , A ( D ) ) , a set S of vertices of D is a kernel of D if it satisfies that: (i) for \( u,v\in S\) u , v S , \( (u,v) \notin A(D)\) ( u , v ) A ( D ) and (ii) for every \(u \in V(D)\setminus S\) u V ( D ) \ S , there exists \(v \in S\) v S , such that \((u,v) \in A(D)\) ( u , v ) A ( D ) . One of the most important results about kernels in digraphs is the following one, due to M. Richardson: Every digraph with no odd cycles has a kernel. The work and history of Graph Theory in Mexico is deeply woven with the study of kernels in digraphs and, particularly, with the work on Richardson’s theorem along with several generalizations of this result. In this paper, we provide a thorough review of this result and its generalizations.