<p>Let <i>G</i> be a graph with order <i>n</i> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_588_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(\overline{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover> <mi>G</mi> <mo>¯</mo> </mover> </math></EquationSource> </InlineEquation> be its complement. In 1956, Nordhaus and Gaddum showed that <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_588_Article_IEq3.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="210" /> </InlineMediaObject> <EquationSource Format="TEX">\(2\sqrt{n}\leqslant \chi (G)+\chi (\overline{G})\leqslant n+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msqrt> <mi>n</mi> </msqrt> <mo>⩽</mo> <mi>χ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>χ</mi> <mrow> <mo stretchy="false">(</mo> <mover> <mi>G</mi> <mo>¯</mo> </mover> <mo stretchy="false">)</mo> </mrow> <mo>⩽</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_588_Article_IEq4.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="203" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\leqslant \chi (G)\chi (\overline{G})\leqslant (n+1)^{2}/4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>⩽</mo> <mi>χ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mi>χ</mi> <mrow> <mo stretchy="false">(</mo> <mover> <mi>G</mi> <mo>¯</mo> </mover> <mo stretchy="false">)</mo> </mrow> <mo>⩽</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_588_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_588_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi (\overline{G})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mover> <mi>G</mi> <mo>¯</mo> </mover> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> are the chromatic numbers of <i>G</i> and <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40305_2025_588_Article_IEq7.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(\overline{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover> <mi>G</mi> <mo>¯</mo> </mover> </math></EquationSource> </InlineEquation>, respectively. The Nordhaus–Gaddum-type problems focus on the sum or product of some invariants of a graph and its complement. In this paper, we introduce an edge-shift operation and determine the extremal hypergraphs, which attain the extremal value of the sum of spectral radius or transversals for a uniform hypergraph and its complement. The spectral radius is the maximal absolute value of eigenvalues of the adjacency tensor of a hypergraph, and transversal number is the minimum cardinality of a vertex subset, which has a nonempty intersection with each edge. Furthermore, we also discuss some relations between spectral invariants and transversal numbers of uniform hypergraphs.</p>

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

Some Nordhaus–Gaddum-Type Results on Spectral Radius and Transversals of Uniform Hypergraphs

  • Yuan Hou,
  • Wei Li,
  • Wen-Huan Wang

摘要

Let G be a graph with order n and \(\overline{G}\) G ¯ be its complement. In 1956, Nordhaus and Gaddum showed that \(2\sqrt{n}\leqslant \chi (G)+\chi (\overline{G})\leqslant n+1\) 2 n χ ( G ) + χ ( G ¯ ) n + 1 and \(n\leqslant \chi (G)\chi (\overline{G})\leqslant (n+1)^{2}/4\) n χ ( G ) χ ( G ¯ ) ( n + 1 ) 2 / 4 , where \(\chi (G)\) χ ( G ) and \(\chi (\overline{G})\) χ ( G ¯ ) are the chromatic numbers of G and \(\overline{G}\) G ¯ , respectively. The Nordhaus–Gaddum-type problems focus on the sum or product of some invariants of a graph and its complement. In this paper, we introduce an edge-shift operation and determine the extremal hypergraphs, which attain the extremal value of the sum of spectral radius or transversals for a uniform hypergraph and its complement. The spectral radius is the maximal absolute value of eigenvalues of the adjacency tensor of a hypergraph, and transversal number is the minimum cardinality of a vertex subset, which has a nonempty intersection with each edge. Furthermore, we also discuss some relations between spectral invariants and transversal numbers of uniform hypergraphs.