Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\alpha (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> denote the cardinality of a maximum independent set and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mu (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be the size of a maximum matching of a graph <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$G=\left( V\left( G\right) ,E\left( G\right) \right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mfenced close=")" open="("> <mi>V</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> <mo>,</mo> <mi>E</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. If <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\alpha (G)+\mu (G)=\left| V\left( G\right) \right| -k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>μ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfenced close="|" open="|"> <mi>V</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mfenced> <mo>-</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>, then G is a k -König–Egerváry graph. In particular, if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$k=0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, then G is a König–Egerváry graph. The corona <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$H\circ \mathcal {X}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mo>∘</mo> <mi mathvariant="script">X</mi> </mrow> </math></EquationSource> </InlineEquation> of a graph H and a family of graphs <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\mathcal {X}=\left\{ X_{i}:1\le i\le \left| V(H)\right| \right\} $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">X</mi> <mo>=</mo> <mfenced close="}" open="{"> <msub> <mi>X</mi> <mi>i</mi> </msub> <mo>:</mo> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mfenced close="|" open="|"> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mfenced> </mfenced> </mrow> </math></EquationSource> </InlineEquation> is obtained by joining each vertex <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$v_{i}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>v</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> of H to all the vertices of the corresponding graph <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$X_{i},i=1,2,...,\left| V(H)\right| $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>X</mi> <mi>i</mi> </msub> <mo>,</mo> <mi>i</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mfenced close="|" open="|"> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mfenced> </mrow> </math></EquationSource> </InlineEquation>.In this paper we completely characterize graphs whose coronas are k-König–Egerváry graphs, where <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$k\in \left\{ 0,1\right\} $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>∈</mo> <mfenced close="}" open="{"> <mn>0</mn> <mo>,</mo> <mn>1</mn> </mfenced> </mrow> </math></EquationSource> </InlineEquation>.

On König–Egerváry corona graphs

期刊论文
发表日期：

2025年8月21日

查看全文

Vadim E. Levit,
Eugen Mandrescu

摘要

Let $\alpha (G)$ $α (G)$ denote the cardinality of a maximum independent set and $\mu (G)$ $μ (G)$ be the size of a maximum matching of a graph $G=\left( V\left( G\right) ,E\left( G\right) \right) $ $G = (V (G), E (G))$ . If $\alpha (G)+\mu (G)=\left| V\left( G\right) \right| -k$ $α (G) + μ (G) = |V, (G)| - k$ , then G is a k -König–Egerváry graph. In particular, if $k=0$ $k = 0$ , then G is a König–Egerváry graph. The corona $H\circ \mathcal {X}$ $H \circ X$ of a graph H and a family of graphs $\mathcal {X}=\left\{ X_{i}:1\le i\le \left| V(H)\right| \right\} $ $X = \{X_{i} : 1 \leq i \leq |V (H)|\}$ is obtained by joining each vertex $v_{i}$ $v_{i}$ of H to all the vertices of the corresponding graph $X_{i},i=1,2,...,\left| V(H)\right| $ $X_{i}, i = 1, 2, . . ., |V (H)|$ .

In this paper we completely characterize graphs whose coronas are k-König–Egerváry graphs, where $k\in \left\{ 0,1\right\} $ $k \in \{0, 1\}$ .