For a fixed graph F, a graph G is F-saturated if G does not contain F as a subgraph, but adding any edge in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq3.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$E(\overline{G})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo stretchy="false">(</mo> <mover> <mi>G</mi> <mo>¯</mo> </mover> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> will result in a copy of F. The minimum size of an F-saturated graph of order n is called the saturation number of F, denoted by sat(n, F). In this paper, we are interested in saturation problem of graph <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$K_1\vee {P_t}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>∨</mo> <msub> <mi>P</mi> <mi>t</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq5.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$t\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. As some known results, <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="110" /> </InlineMediaObject> <EquationSource Format="TEX">$sat(n,K_1\vee {P_t})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>a</mi> <mi>t</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>∨</mo> <msub> <mi>P</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is determined for <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq7.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">$2\le t\le 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>≤</mo> <mi>t</mi> <mo>≤</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>. We will show that <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="300" /> </InlineMediaObject> <EquationSource Format="TEX">$sat(n,K_1\vee {P_t})=(n-1)+sat(n-1,P_t)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>a</mi> <mi>t</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>∨</mo> <msub> <mi>P</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>s</mi> <mi>a</mi> <mi>t</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo>,</mo> <msub> <mi>P</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq9.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$t\ge 5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> and n sufficiently large. Moreover, <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">$(K_1\vee {P_t})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>∨</mo> <msub> <mi>P</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-saturated graphs with <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1256_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="110" /> </InlineMediaObject> <EquationSource Format="TEX">$sat(n,K_1\vee {P_t})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>a</mi> <mi>t</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>K</mi> <mn>1</mn> </msub> <mo>∨</mo> <msub> <mi>P</mi> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> edges are characterized.

$(K_{1}\vee {P_{t})}$-saturated graphs with minimum number of edges

期刊论文
发表日期：

2025年1月20日

查看全文

Jinze Hu,
Shengjin Ji,
Qing Cui

摘要

For a fixed graph F, a graph G is F-saturated if G does not contain F as a subgraph, but adding any edge in $E(\overline{G})$ $E (\bar{G})$ will result in a copy of F. The minimum size of an F-saturated graph of order n is called the saturation number of F, denoted by sat(n, F). In this paper, we are interested in saturation problem of graph $K_1\vee {P_t}$ $K_{1} \lor P_{t}$ for $t\ge 2$ $t \geq 2$ . As some known results, $sat(n,K_1\vee {P_t})$ $s a t (n, K_{1} \lor P_{t})$ is determined for $2\le t\le 4$ $2 \leq t \leq 4$ . We will show that $sat(n,K_1\vee {P_t})=(n-1)+sat(n-1,P_t)$ $s a t (n, K_{1} \lor P_{t}) = (n - 1) + s a t (n - 1, P_{t})$ for $t\ge 5$ $t \geq 5$ and n sufficiently large. Moreover, $(K_1\vee {P_t})$ $(K_{1} \lor P_{t})$ -saturated graphs with $sat(n,K_1\vee {P_t})$ $s a t (n, K_{1} \lor P_{t})$ edges are characterized.

\((K_{1}\vee {P_{t})}\)-saturated graphs with minimum number of edges

摘要