<p>The Seymour’s Second Neighborhood Conjecture (SSNC) asserts that every oriented graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation> contains a vertex <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(v\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>v</mi> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(|N^{++}(v)| \ge |N^+(v)|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msup> <mi>N</mi> <mrow> <mo>+</mo> <mo>+</mo> </mrow> </msup> <mrow> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> <mo>≥</mo> <mo stretchy="false">|</mo> </mrow> <msup> <mi>N</mi> <mo>+</mo> </msup> <mrow> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. Such a vertex is said to have the second neighborhood property. The conjecture was first proved for tournaments by Fisher and later Havet and Thomassé provided a different proof using the median order approach. Following this approach, we give another simple proof that the SSNC holds for a tournament missing a matching and a tournament missing a star. Let <i>s</i>,&#xa0;<i>t</i> be two non-negative integers. Denote <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\mathcal {D}_{s,t}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">D</mi> <mrow> <mi>s</mi> <mo>,</mo> <mi>t</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> the class of oriented graphs whose vertex set has a partition <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\((A,B)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>A</mi> <mo>,</mo> <mi>B</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> such that the subgraph induced by <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(A\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>A</mi> </math></EquationSource> </InlineEquation> is <i>s</i>-degenerate and the subgraph induced by <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(B\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>B</mi> </math></EquationSource> </InlineEquation> is <i>t</i>-degenerate. In this paper, we show that the SSNC holds for oriented graphs in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\mathcal {D}_{0,3}\cup \mathcal {D}_{1,1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="script">D</mi> <mrow> <mn>0</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> <mo>∪</mo> <msub> <mi mathvariant="script">D</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>. In [<CitationRef CitationID="CR3">3</CitationRef>], Dara, Francis, Jacob and Narayanan showed that the conjecture holds for oriented graphs in <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\mathcal {D}_{0,2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">D</mi> <mrow> <mn>0</mn> <mo>,</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>. Thus, we extend their result.</p>

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

Seymour’s second neighborhood conjecture for some oriented graphs

  • Haozhe Wang,
  • Mei Lu

摘要

The Seymour’s Second Neighborhood Conjecture (SSNC) asserts that every oriented graph \(G\) G contains a vertex \(v\) v such that \(|N^{++}(v)| \ge |N^+(v)|\) | N + + ( v ) | | N + ( v ) | . Such a vertex is said to have the second neighborhood property. The conjecture was first proved for tournaments by Fisher and later Havet and Thomassé provided a different proof using the median order approach. Following this approach, we give another simple proof that the SSNC holds for a tournament missing a matching and a tournament missing a star. Let st be two non-negative integers. Denote \(\mathcal {D}_{s,t}\) D s , t the class of oriented graphs whose vertex set has a partition \((A,B)\) ( A , B ) such that the subgraph induced by \(A\) A is s-degenerate and the subgraph induced by \(B\) B is t-degenerate. In this paper, we show that the SSNC holds for oriented graphs in \(\mathcal {D}_{0,3}\cup \mathcal {D}_{1,1}\) D 0 , 3 D 1 , 1 . In [3], Dara, Francis, Jacob and Narayanan showed that the conjecture holds for oriented graphs in \(\mathcal {D}_{0,2}\) D 0 , 2 . Thus, we extend their result.