<p>We show that some well-known integer sequences can be represented as sequences of determinant of matrices associated with certain families of threshold graphs. Specifically, let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> denote a connected threshold graph with <i>n</i> vertices. Define <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(S(G_n):=(s_{ij})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>:</mo> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <msub> <mi>s</mi> <mrow> <mi mathvariant="italic">ij</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> as the <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(n \times n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> matrix, where <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(s_{ii}=0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>s</mi> <mrow> <mi mathvariant="italic">ii</mi> </mrow> </msub> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> for all <i>i</i>; <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(s_{ij}=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>s</mi> <mrow> <mi mathvariant="italic">ij</mi> </mrow> </msub> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> if vertices <i>i</i> and <i>j</i> are not adjacent, and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> if <i>i</i> and <i>j</i> are adjacent. We show that if <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\{\mu _{j-1}\}_{j \ge 1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mo stretchy="false">{</mo> <msub> <mi>μ</mi> <mrow> <mi>j</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">}</mo> </mrow> <mrow> <mi>j</mi> <mo>≥</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> is the sequence of Pell numbers, then <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\mu _{j-1}=|\det \,S(A_j)|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>μ</mi> <mrow> <mi>j</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mrow> <mo stretchy="false">|</mo> <mo movablelimits="true">det</mo> <mspace width="0.166667em" /> <mi>S</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>A</mi> <mi>j</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(A_j\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>A</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> is the connected antiregular graph on <i>j</i> vertices. We then find a sequence of connected threshold graphs <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\{G_m\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <msub> <mi>G</mi> <mi>m</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> such that the sequence of Fibonacci numbers aligns with <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\{|\det \, S(G_m)|\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mo stretchy="false">|</mo> <mo movablelimits="true">det</mo> <mspace width="0.166667em" /> <mi>S</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mi>m</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. Additionally, we determine a recurrence relation for the sequence <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\{\det \, D(A_k)\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mo movablelimits="true">det</mo> <mspace width="0.166667em" /> <mi>D</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>A</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(D(A_k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo stretchy="false">(</mo> <msub> <mi>A</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is the distance matrix of the connected antiregular threshold graph with <i>k</i> vertices. Using this relation, we give an explicit formula to compute <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\det \, D(A_k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">det</mo> <mspace width="0.166667em" /> <mi>D</mi> <mo stretchy="false">(</mo> <msub> <mi>A</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Integer Sequences Generated by the Determinants of Matrices Associated with Threshold Graphs

  • Ramamurthy Balaji,
  • Gargi Lather,
  • Vinayak Gupta

摘要

We show that some well-known integer sequences can be represented as sequences of determinant of matrices associated with certain families of threshold graphs. Specifically, let \(G_n\) G n denote a connected threshold graph with n vertices. Define \(S(G_n):=(s_{ij})\) S ( G n ) : = ( s ij ) as the \(n \times n\) n × n matrix, where \(s_{ii}=0\) s ii = 0 for all i; \(s_{ij}=1\) s ij = 1 if vertices i and j are not adjacent, and \(-1\) - 1 if i and j are adjacent. We show that if \(\{\mu _{j-1}\}_{j \ge 1}\) { μ j - 1 } j 1 is the sequence of Pell numbers, then \(\mu _{j-1}=|\det \,S(A_j)|\) μ j - 1 = | det S ( A j ) | , where \(A_j\) A j is the connected antiregular graph on j vertices. We then find a sequence of connected threshold graphs \(\{G_m\}\) { G m } such that the sequence of Fibonacci numbers aligns with \(\{|\det \, S(G_m)|\}\) { | det S ( G m ) | } . Additionally, we determine a recurrence relation for the sequence \(\{\det \, D(A_k)\}\) { det D ( A k ) } , where \(D(A_k)\) D ( A k ) is the distance matrix of the connected antiregular threshold graph with k vertices. Using this relation, we give an explicit formula to compute \(\det \, D(A_k)\) det D ( A k ) .