A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases its toughness, where t is a positive real number. We say G is <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(P_2\cup 3P_1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <mn>3</mn> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free if it does not contain <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$P_2\cup 3P_1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <mn>3</mn> <msub> <mi>P</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> as an induced subgraph. In this paper, we present two non-hamiltonian 1-tough <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$(P_2\cup 3P_1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <mn>3</mn> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free graphs and completely determine the structure of minimally 1-tough <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$(P_2\cup 3P_1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <mn>3</mn> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free graphs, thereby confirming that the minimum degree of each minimally 1-tough <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$(P_2\cup 3P_1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo>∪</mo> <mn>3</mn> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-free graph is two.

On Minimally 1-tough $(P_2\cup 3P_1)$-Free Graphs

期刊论文
发表日期：

2026年4月7日

查看全文

Shiyu Cao,
Jing Chen

摘要

A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases its toughness, where t is a positive real number. We say G is $(P_2\cup 3P_1)$ $(P_{2} \cup 3 P_{1})$ -free if it does not contain $P_2\cup 3P_1$ $P_{2} \cup 3 P_{1}$ as an induced subgraph. In this paper, we present two non-hamiltonian 1-tough $(P_2\cup 3P_1)$ $(P_{2} \cup 3 P_{1})$ -free graphs and completely determine the structure of minimally 1-tough $(P_2\cup 3P_1)$ $(P_{2} \cup 3 P_{1})$ -free graphs, thereby confirming that the minimum degree of each minimally 1-tough $(P_2\cup 3P_1)$ $(P_{2} \cup 3 P_{1})$ -free graph is two.

On Minimally 1-tough \((P_2\cup 3P_1)\)-Free Graphs

摘要