<p>Let <i>G</i> be a graph. The edge blow-up graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G^{p+1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>G</mi> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> of <i>G</i> is a graph obtained by replacing each edge of <i>G</i> with a clique of order <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(p+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, where the new vertices of the cliques are all distinct. Denote by <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(K_t^-\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>K</mi> <mi>t</mi> <mo>-</mo> </msubsup> </math></EquationSource> </InlineEquation> the graph obtained from the complete graph <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(K_t\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation> by removing one edge. In this paper, we construct two classes of edge blow-up graphs, namely the string graph and the ring graph associated with <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(K_t^-\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>K</mi> <mi>t</mi> <mo>-</mo> </msubsup> </math></EquationSource> </InlineEquation>, which are denoted <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(S(K_r^-, K_m^-, n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo stretchy="false">(</mo> <msubsup> <mi>K</mi> <mi>r</mi> <mo>-</mo> </msubsup> <mo>,</mo> <msubsup> <mi>K</mi> <mi>m</mi> <mo>-</mo> </msubsup> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(R(K_r^-, K_m^-, n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msubsup> <mi>K</mi> <mi>r</mi> <mo>-</mo> </msubsup> <mo>,</mo> <msubsup> <mi>K</mi> <mi>m</mi> <mo>-</mo> </msubsup> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, respectively, with <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(r, m \ge 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>,</mo> <mi>m</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>. Specifically, for a path <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(P_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>, we alternately replace each edge of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(P_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(K_r^-\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>K</mi> <mi>r</mi> <mo>-</mo> </msubsup> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(K_m^-\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>K</mi> <mi>m</mi> <mo>-</mo> </msubsup> </math></EquationSource> </InlineEquation>. For a cycle <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(C_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>, we alternately replace each edge of <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(C_{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(K_r^-\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>K</mi> <mi>r</mi> <mo>-</mo> </msubsup> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(K_m^-\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>K</mi> <mi>m</mi> <mo>-</mo> </msubsup> </math></EquationSource> </InlineEquation>, where <i>n</i> is even. This construction produces the string graph <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(S(K_r^-, K_m^-, n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo stretchy="false">(</mo> <msubsup> <mi>K</mi> <mi>r</mi> <mo>-</mo> </msubsup> <mo>,</mo> <msubsup> <mi>K</mi> <mi>m</mi> <mo>-</mo> </msubsup> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and the ring graph <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(R(K_r^-, K_m^-, n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo stretchy="false">(</mo> <msubsup> <mi>K</mi> <mi>r</mi> <mo>-</mo> </msubsup> <mo>,</mo> <msubsup> <mi>K</mi> <mi>m</mi> <mo>-</mo> </msubsup> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Using combinatorial and electrical network methods, we derive formulas for the resistance distances in these two classes of graphs.</p>

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

Enumeration of Resistance Distances for Two Classes of Edge Blow-Up Graphs

  • Liang Chen,
  • Lu Li,
  • Hechao Liu,
  • Lingli Cheng,
  • Shouyou Huang

摘要

Let G be a graph. The edge blow-up graph \(G^{p+1}\) G p + 1 of G is a graph obtained by replacing each edge of G with a clique of order \(p+1\) p + 1 , where the new vertices of the cliques are all distinct. Denote by \(K_t^-\) K t - the graph obtained from the complete graph \(K_t\) K t by removing one edge. In this paper, we construct two classes of edge blow-up graphs, namely the string graph and the ring graph associated with \(K_t^-\) K t - , which are denoted \(S(K_r^-, K_m^-, n)\) S ( K r - , K m - , n ) and \(R(K_r^-, K_m^-, n)\) R ( K r - , K m - , n ) , respectively, with \(r, m \ge 4\) r , m 4 . Specifically, for a path \(P_{n}\) P n , we alternately replace each edge of \(P_{n}\) P n with \(K_r^-\) K r - and \(K_m^-\) K m - . For a cycle \(C_{n}\) C n , we alternately replace each edge of \(C_{n}\) C n with \(K_r^-\) K r - and \(K_m^-\) K m - , where n is even. This construction produces the string graph \(S(K_r^-, K_m^-, n)\) S ( K r - , K m - , n ) and the ring graph \(R(K_r^-, K_m^-, n)\) R ( K r - , K m - , n ) . Using combinatorial and electrical network methods, we derive formulas for the resistance distances in these two classes of graphs.