<p>For an <i>n</i>-vertex graph <i>G</i>, the walk matrix of <i>G</i>, denoted by <i>W</i>(<i>G</i>), is the matrix <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\([e,A(G)e,\ldots ,(A(G))^{n-1}e]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mi>e</mi> <mo>,</mo> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mi>e</mi> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mi>e</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>A</i>(<i>G</i>) is the adjacency matrix of <i>G</i> and <i>e</i> is the all-ones vector. For two integers <i>m</i> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(1\le \ell \le (m+1)/2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>ℓ</mi> <mo>≤</mo> <mo stretchy="false">(</mo> <mi>m</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, let <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(G\circ P_m^{(\ell )}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <msubsup> <mi>P</mi> <mi>m</mi> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> </msubsup> </mrow> </math></EquationSource> </InlineEquation> be the rooted product of <i>G</i> and the path <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(P_m\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation> taking the <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-th vertex of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(P_m\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation> as the root, i.e., <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(G\circ P_m^{(\ell )}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <msubsup> <mi>P</mi> <mi>m</mi> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> </msubsup> </mrow> </math></EquationSource> </InlineEquation> is a graph obtained from <i>G</i> and <i>n</i> copies of the path <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(P_m\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation> by identifying the <i>i</i>-th vertex of <i>G</i> with the <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-th vertex (the root vertex) of the <i>i</i>-th copy of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(P_m\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>m</mi> </msub> </math></EquationSource> </InlineEquation> for each <i>i</i>. We prove that <Equation ID="Equ21"> <EquationSource Format="TEX">\(\begin{aligned} \det W(G\circ P_m^{(\ell )}) = {\left\{ \begin{array}{ll} \pm (\det A(G))^{\lfloor \frac{m}{2}\rfloor }(\det W(G))^m, &amp; \text {if }\gcd (\ell ,m+1)=1, \\ 0,&amp; \text {otherwise.} \end{array}\right. } \end{aligned}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <mo movablelimits="true">det</mo> <mi>W</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>∘</mo> <msubsup> <mi>P</mi> <mi>m</mi> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfenced open="{"> <mrow> <mtable> <mtr> <mtd columnalign="left"> <mrow> <mo>±</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mo movablelimits="true">det</mo> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mrow> <mo>⌊</mo> <mfrac> <mi>m</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> </msup> <msup> <mrow> <mo stretchy="false">(</mo> <mo movablelimits="true">det</mo> <mi>W</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mi>m</mi> </msup> <mo>,</mo> </mrow> </mtd> <mtd columnalign="left"> <mrow> <mtext>if</mtext> <mspace width="0.333333em" /> <mo movablelimits="true">gcd</mo> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi>m</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo>,</mo> </mrow> </mtd> </mtr> <mtr> <mtd columnalign="left"> <mrow> <mrow /> <mn>0</mn> <mo>,</mo> </mrow> </mtd> <mtd columnalign="left"> <mtext>otherwise.</mtext> </mtd> </mtr> </mtable> </mrow> </mfenced> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation>This extends a recent result established in [Wang et al. Linear Multilinear Algebra 72 (2024): 828–840], which corresponds to the special case <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\ell =1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. As a direct application, we prove that if <i>G</i> satisfies <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\det A(G)=\pm 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">det</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>±</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\det W(G)=\pm 2^{\lfloor n/2\rfloor }\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">det</mo> <mi>W</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mo>±</mo> <msup> <mn>2</mn> <mrow> <mo>⌊</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo>⌋</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, then for any sequence of integer pairs <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\{(m_i,\ell _i)\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mrow> <mo stretchy="false">(</mo> <msub> <mi>m</mi> <mi>i</mi> </msub> <mo>,</mo> <msub> <mi>ℓ</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(\gcd (\ell _i,m_i+1)=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">gcd</mo> <mo stretchy="false">(</mo> <msub> <mi>ℓ</mi> <mi>i</mi> </msub> <mo>,</mo> <msub> <mi>m</mi> <mi>i</mi> </msub> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for each <i>i</i>, all the graphs in the family <Equation ID="Equ22"> <EquationSource Format="TEX">\(\begin{aligned} G\circ P_{m_1}^{(\ell _1)}, (G\circ P_{m_1}^{(\ell _1)})\circ P_{m_2}^{(\ell _2)}, ((G\circ P_{m_1}^{(\ell _1)})\circ P_{m_2}^{(\ell _2)})\circ P_{m_3}^{(\ell _3)},\ldots \end{aligned}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <mi>G</mi> <mo>∘</mo> <msubsup> <mi>P</mi> <mrow> <msub> <mi>m</mi> <mn>1</mn> </msub> </mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>ℓ</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </msubsup> <mo>,</mo> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>∘</mo> <msubsup> <mi>P</mi> <mrow> <msub> <mi>m</mi> <mn>1</mn> </msub> </mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>ℓ</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>∘</mo> <msubsup> <mi>P</mi> <mrow> <msub> <mi>m</mi> <mn>2</mn> </msub> </mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>ℓ</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </msubsup> <mo>,</mo> <mrow> <mo stretchy="false">(</mo> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>∘</mo> <msubsup> <mi>P</mi> <mrow> <msub> <mi>m</mi> <mn>1</mn> </msub> </mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>ℓ</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>∘</mo> <msubsup> <mi>P</mi> <mrow> <msub> <mi>m</mi> <mn>2</mn> </msub> </mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>ℓ</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </msubsup> <mo stretchy="false">)</mo> </mrow> <mo>∘</mo> <msubsup> <mi>P</mi> <mrow> <msub> <mi>m</mi> <mn>3</mn> </msub> </mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>ℓ</mi> <mn>3</mn> </msub> <mo stretchy="false">)</mo> </mrow> </msubsup> <mo>,</mo> <mo>…</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation>are determined by their generalized spectrum.</p>

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

On the determinant of the walk matrix of the rooted product with a path

  • Zhidan Yan,
  • Wei Wang

摘要

For an n-vertex graph G, the walk matrix of G, denoted by W(G), is the matrix \([e,A(G)e,\ldots ,(A(G))^{n-1}e]\) [ e , A ( G ) e , , ( A ( G ) ) n - 1 e ] , where A(G) is the adjacency matrix of G and e is the all-ones vector. For two integers m and \(\ell \) with \(1\le \ell \le (m+1)/2\) 1 ( m + 1 ) / 2 , let \(G\circ P_m^{(\ell )}\) G P m ( ) be the rooted product of G and the path \(P_m\) P m taking the \(\ell \) -th vertex of \(P_m\) P m as the root, i.e., \(G\circ P_m^{(\ell )}\) G P m ( ) is a graph obtained from G and n copies of the path \(P_m\) P m by identifying the i-th vertex of G with the \(\ell \) -th vertex (the root vertex) of the i-th copy of \(P_m\) P m for each i. We prove that \(\begin{aligned} \det W(G\circ P_m^{(\ell )}) = {\left\{ \begin{array}{ll} \pm (\det A(G))^{\lfloor \frac{m}{2}\rfloor }(\det W(G))^m, & \text {if }\gcd (\ell ,m+1)=1, \\ 0,& \text {otherwise.} \end{array}\right. } \end{aligned}\) det W ( G P m ( ) ) = ± ( det A ( G ) ) m 2 ( det W ( G ) ) m , if gcd ( , m + 1 ) = 1 , 0 , otherwise. This extends a recent result established in [Wang et al. Linear Multilinear Algebra 72 (2024): 828–840], which corresponds to the special case \(\ell =1\) = 1 . As a direct application, we prove that if G satisfies \(\det A(G)=\pm 1\) det A ( G ) = ± 1 and \(\det W(G)=\pm 2^{\lfloor n/2\rfloor }\) det W ( G ) = ± 2 n / 2 , then for any sequence of integer pairs \(\{(m_i,\ell _i)\}\) { ( m i , i ) } with \(\gcd (\ell _i,m_i+1)=1\) gcd ( i , m i + 1 ) = 1 for each i, all the graphs in the family \(\begin{aligned} G\circ P_{m_1}^{(\ell _1)}, (G\circ P_{m_1}^{(\ell _1)})\circ P_{m_2}^{(\ell _2)}, ((G\circ P_{m_1}^{(\ell _1)})\circ P_{m_2}^{(\ell _2)})\circ P_{m_3}^{(\ell _3)},\ldots \end{aligned}\) G P m 1 ( 1 ) , ( G P m 1 ( 1 ) ) P m 2 ( 2 ) , ( ( G P m 1 ( 1 ) ) P m 2 ( 2 ) ) P m 3 ( 3 ) , are determined by their generalized spectrum.