Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathscr {G}=\{G_1, G_2, \ldots , G_s\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">G</mi> <mo>=</mo> <mo stretchy="false">{</mo> <msub> <mi>G</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>G</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>G</mi> <mi>s</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> be a collection of s not necessarily distinct n-vertices graphs on the same vertex set V. A graph H on the vertex set V is a partial <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathscr {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>-transversal if there is an injection <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\phi $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϕ</mi> </math></EquationSource> </InlineEquation> from <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$E(H)\rightarrow \{1, \cdots , s\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo stretchy="false">→</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>s</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> such that for every <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$e\in E(H)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>∈</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, we have <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$e\in E(G_{\phi (s)})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>∈</mo> <mi>E</mi> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mrow> <mi>ϕ</mi> <mo stretchy="false">(</mo> <mi>s</mi> <mo stretchy="false">)</mo> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. If, in addition, <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$|E(H)|=s$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>=</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation>, then H is a <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\mathscr {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>-transversal, or we say H is rainbow. In this paper, we obtain the following two results on the partial <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\mathscr {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>-transversals. <DefinitionList> <DefinitionListEntry> <Term>(i)</Term> <Description> For <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\mathscr {G}=\{G_1, G_2, \ldots , G_n\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">G</mi> <mo>=</mo> <mo stretchy="false">{</mo> <msub> <mi>G</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>G</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>G</mi> <mi>n</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$S=\{v\in V: d_{G_i}(v)\ge \frac{n}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>=</mo> <mo stretchy="false">{</mo> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo>:</mo> <msub> <mi>d</mi> <msub> <mi>G</mi> <mi>i</mi> </msub> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> for every <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$i\in [n]\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, if <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$|S|\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>S</mi> <mo stretchy="false">|</mo> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, then there is a cycle partial <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\mathscr {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>-transversal containing S. </Description> </DefinitionListEntry> <DefinitionListEntry> <Term>(ii)</Term> <Description> For <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$\mathscr {G}=\{G_1, G_2, \ldots , G_{n-1}\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">G</mi> <mo>=</mo> <mo stretchy="false">{</mo> <msub> <mi>G</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>G</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>G</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, if <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$G_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> is connected with <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\varepsilon (G_i)>\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) +2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>></mo> <mfenced close=")" open="("> <mrow> <mtable> <mtr> <mtd> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </mtd> </mtr> <mtr> <mtd> <mrow> <mrow /> <mn>2</mn> </mrow> </mtd> </mtr> </mtable> </mrow> </mfenced> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$i=1, 2, \cdots , n-1,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> then <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$\mathscr {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation> admits a rainbow Hamiltonian path. </Description> </DefinitionListEntry> </DefinitionList>

Rainbow Hamiltonicity with large edge numbers

期刊论文
发表日期：

2025年10月23日

查看全文

Xia Liu,
Shuo Zhang,
Miao Wang

摘要

Let $\mathscr {G}=\{G_1, G_2, \ldots , G_s\}$ $G = {G_{1}, G_{2}, \dots, G_{s}}$ be a collection of s not necessarily distinct n-vertices graphs on the same vertex set V. A graph H on the vertex set V is a partial $\mathscr {G}$ $G$ -transversal if there is an injection $\phi $ $ϕ$ from $E(H)\rightarrow \{1, \cdots , s\}$ $E (H) \to {1, \dots, s}$ such that for every $e\in E(H)$ $e \in E (H)$ , we have $e\in E(G_{\phi (s)})$ $e \in E (G_{ϕ (s)})$ . If, in addition, $|E(H)|=s$ $| E (H) | = s$ , then H is a $\mathscr {G}$ $G$ -transversal, or we say H is rainbow. In this paper, we obtain the following two results on the partial $\mathscr {G}$ $G$ -transversals. (i)

For $\mathscr {G}=\{G_1, G_2, \ldots , G_n\}$ $G = {G_{1}, G_{2}, \dots, G_{n}}$ and $S=\{v\in V: d_{G_i}(v)\ge \frac{n}{2}$ $S = {v \in V : d_{G_{i}} (v) \geq \frac{n}{2}$ for every $i\in [n]\}$ $i \in [n]}$ , if $|S|\ge 2$ $| S | \geq 2$ , then there is a cycle partial $\mathscr {G}$ $G$ -transversal containing S.

(ii)

For $\mathscr {G}=\{G_1, G_2, \ldots , G_{n-1}\}$ $G = {G_{1}, G_{2}, \dots, G_{n - 1}}$ , if $G_i$ $G_{i}$ is connected with $\varepsilon (G_i)>\left( {\begin{array}{c}n-2\\ 2\end{array}}\right) +2$ $ε (G_{i}) > (\begin{matrix} n - 2 \\ 2 \end{matrix}) + 2$ for $i=1, 2, \cdots , n-1,$ $i = 1, 2, \dots, n - 1,$ then $\mathscr {G}$ $G$ admits a rainbow Hamiltonian path.