<p>Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G=(V,E)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be a simple graph and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\overline{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover> <mi>G</mi> <mo>¯</mo> </mover> </math></EquationSource> </InlineEquation> be its complement. It is well-known that the matching polynomial of <i>G</i> is completely determined by that of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\overline{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover> <mi>G</mi> <mo>¯</mo> </mover> </math></EquationSource> </InlineEquation>. We are curious about what one can deduce if <i>G</i> is a self-complementary graph. Suppose that <i>G</i> is a self-complementary graph with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(n=4t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>4</mn> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(4t+1 (t\ge 1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>4</mn> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">(</mo> <mi>t</mi> <mo>≥</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> vertices, and its matching polynomial is <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\mu (G,x)=\sum _{r=0}^{2t}(-1)^{r}p(G,r)x^{n-2r}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msubsup> <mo>∑</mo> <mrow> <mi>r</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mn>2</mn> <mi>t</mi> </mrow> </msubsup> <msup> <mrow> <mo stretchy="false">(</mo> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>r</mi> </msup> <mi>p</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>x</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> <mi>r</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we first deduce that the coefficients of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\mu (G,x)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> satisfy the recurrent relation <Equation ID="Equ5"> <EquationSource Format="TEX">\(\begin{aligned} p(G,2r+1)=\frac{1}{2}\sum _{i=0}^{2r}(-1)^{i}p(G,i)p(K_{n-2i},2r-i+1), \ \ 0\le r\le t-1, \end{aligned}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <mi>p</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mn>2</mn> <mi>r</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <munderover> <mo>∑</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mn>2</mn> <mi>r</mi> </mrow> </munderover> <msup> <mrow> <mo stretchy="false">(</mo> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>i</mi> </msup> <mi>p</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>i</mi> <mo stretchy="false">)</mo> </mrow> <mi>p</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> <mi>i</mi> </mrow> </msub> <mo>,</mo> <mn>2</mn> <mi>r</mi> <mo>-</mo> <mi>i</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> <mspace width="4pt" /> <mspace width="4pt" /> <mn>0</mn> <mo>≤</mo> <mi>r</mi> <mo>≤</mo> <mi>t</mi> <mo>-</mo> <mn>1</mn> <mo>,</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation>where <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(K_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> denotes the complete graph of order <i>n</i>. Then we show that, in addition to <i>p</i>(<i>G</i>,&#xa0;2), <i>p</i>(<i>G</i>,&#xa0;3) is also completely determined by the degree sequence of <i>G</i>, and the explicit expressions in terms of its degree sequence are given. Finally, <i>p</i>(<i>G</i>,&#xa0;2) and <i>p</i>(<i>G</i>,&#xa0;3) are computed for all self-complementary graphs with <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(n\le 13\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≤</mo> <mn>13</mn> </mrow> </math></EquationSource> </InlineEquation> vertices.</p>

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

Coefficients of the Matching Polynomial of a Self-Complementary Graph

  • Haiyan Chen,
  • Yinxia Yuan

摘要

Let \(G=(V,E)\) G = ( V , E ) be a simple graph and \(\overline{G}\) G ¯ be its complement. It is well-known that the matching polynomial of G is completely determined by that of \(\overline{G}\) G ¯ . We are curious about what one can deduce if G is a self-complementary graph. Suppose that G is a self-complementary graph with \(n=4t\) n = 4 t or \(4t+1 (t\ge 1)\) 4 t + 1 ( t 1 ) vertices, and its matching polynomial is \(\mu (G,x)=\sum _{r=0}^{2t}(-1)^{r}p(G,r)x^{n-2r}\) μ ( G , x ) = r = 0 2 t ( - 1 ) r p ( G , r ) x n - 2 r . In this paper, we first deduce that the coefficients of \(\mu (G,x)\) μ ( G , x ) satisfy the recurrent relation \(\begin{aligned} p(G,2r+1)=\frac{1}{2}\sum _{i=0}^{2r}(-1)^{i}p(G,i)p(K_{n-2i},2r-i+1), \ \ 0\le r\le t-1, \end{aligned}\) p ( G , 2 r + 1 ) = 1 2 i = 0 2 r ( - 1 ) i p ( G , i ) p ( K n - 2 i , 2 r - i + 1 ) , 0 r t - 1 , where \(K_n\) K n denotes the complete graph of order n. Then we show that, in addition to p(G, 2), p(G, 3) is also completely determined by the degree sequence of G, and the explicit expressions in terms of its degree sequence are given. Finally, p(G, 2) and p(G, 3) are computed for all self-complementary graphs with \(n\le 13\) n 13 vertices.