<p>For a graph <i>H</i> with vertex set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(V(H) =\{1,2,...,k\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>k</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> and a family of vertex disjoint graphs <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(H_1, H_2,...,H_k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>H</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>H</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msub> <mi>H</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, the <i>H</i>-join of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(H_1,H_2,\ldots ,H_k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>H</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>H</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>H</mi> <mi>k</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, denoted by <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(H[H_1,H_2,\ldots ,H_k]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mo stretchy="false">[</mo> <msub> <mi>H</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>H</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>H</mi> <mi>k</mi> </msub> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>, is a graph obtained from <i>H</i> by replacing <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(i^{th}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>i</mi> <mrow> <mi mathvariant="italic">th</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> vertex of <i>H</i> by <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(H_i\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>H</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(1\le i \le k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>, and replacing any edge <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\{l,j\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mi>l</mi> <mo>,</mo> <mi>j</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> of <i>H</i> by the set of new edges <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\{\{u_{l},u_{j}\}: u_{l} \in V(H_l), u_{j} \in V(H_j)\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mrow> <mo stretchy="false">{</mo> <msub> <mi>u</mi> <mi>l</mi> </msub> <mo>,</mo> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo stretchy="false">}</mo> </mrow> <mo>:</mo> <msub> <mi>u</mi> <mi>l</mi> </msub> <mo>∈</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mi>l</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> <msub> <mi>u</mi> <mi>j</mi> </msub> <mo>∈</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mi>j</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we establish a necessary and sufficient condition under which the <i>H</i>-join of Laplacian integral graphs is Laplacian integral. We also give some necessary and sufficient conditions for the graphs <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(H_{n_i}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>H</mi> <msub> <mi>n</mi> <mi>i</mi> </msub> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(1 \le i \le 5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>, so that <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(P_4[H_{n_1}, H_{n_2}, H_{n_3}, H_{n_4}]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>4</mn> </msub> <mrow> <mo stretchy="false">[</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>1</mn> </msub> </msub> <mo>,</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>2</mn> </msub> </msub> <mo>,</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>3</mn> </msub> </msub> <mo>,</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>4</mn> </msub> </msub> <mo stretchy="false">]</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(P_5[H_{n_1}, H_{n_2}, H_{n_3}, H_{n_4}, H_{n_5}]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>5</mn> </msub> <mrow> <mo stretchy="false">[</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>1</mn> </msub> </msub> <mo>,</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>2</mn> </msub> </msub> <mo>,</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>3</mn> </msub> </msub> <mo>,</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>4</mn> </msub> </msub> <mo>,</mo> <msub> <mi>H</mi> <msub> <mi>n</mi> <mn>5</mn> </msub> </msub> <mo stretchy="false">]</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> are Laplacian integral. It is to be noted that these graphs produce infinite family of Laplacian integral graphs which are not cographs. Furthermore, we provide characterizations for the <i>H</i>-join and <i>H</i>-product of constructably Laplacian integral graphs to be constructably Laplacian integral. While proving the above results, we have also given characterizations for <i>H</i>-join and <i>H</i>-product of cographs to be a cograph.</p>

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

On the H-join and H-product of Laplacian and constructably Laplacian integral graphs

  • Komal Kumari,
  • Pratima Panigrahi

摘要

For a graph H with vertex set \(V(H) =\{1,2,...,k\}\) V ( H ) = { 1 , 2 , . . . , k } and a family of vertex disjoint graphs \(H_1, H_2,...,H_k\) H 1 , H 2 , . . . , H k , the H-join of \(H_1,H_2,\ldots ,H_k\) H 1 , H 2 , , H k , denoted by \(H[H_1,H_2,\ldots ,H_k]\) H [ H 1 , H 2 , , H k ] , is a graph obtained from H by replacing \(i^{th}\) i th vertex of H by \(H_i\) H i , \(1\le i \le k\) 1 i k , and replacing any edge \(\{l,j\}\) { l , j } of H by the set of new edges \(\{\{u_{l},u_{j}\}: u_{l} \in V(H_l), u_{j} \in V(H_j)\}\) { { u l , u j } : u l V ( H l ) , u j V ( H j ) } . In this paper, we establish a necessary and sufficient condition under which the H-join of Laplacian integral graphs is Laplacian integral. We also give some necessary and sufficient conditions for the graphs \(H_{n_i}\) H n i , \(1 \le i \le 5\) 1 i 5 , so that \(P_4[H_{n_1}, H_{n_2}, H_{n_3}, H_{n_4}]\) P 4 [ H n 1 , H n 2 , H n 3 , H n 4 ] and \(P_5[H_{n_1}, H_{n_2}, H_{n_3}, H_{n_4}, H_{n_5}]\) P 5 [ H n 1 , H n 2 , H n 3 , H n 4 , H n 5 ] are Laplacian integral. It is to be noted that these graphs produce infinite family of Laplacian integral graphs which are not cographs. Furthermore, we provide characterizations for the H-join and H-product of constructably Laplacian integral graphs to be constructably Laplacian integral. While proving the above results, we have also given characterizations for H-join and H-product of cographs to be a cograph.