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, while <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 in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$G=\left( V,E\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mfenced close=")" open="("> <mi>V</mi> <mo>,</mo> <mi>E</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\xi (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 size of the intersection of all maximum independent sets [<CitationRef CitationID="CR12">12</CitationRef>]. It is known that if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\alpha (G)+\mu (G)=n(G)=\left| V\right| $</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> <mi>n</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfenced close="|" open="|"> <mi>V</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, then G is a König-Egerváry graph [<CitationRef CitationID="CR5">5</CitationRef>, <CitationRef CitationID="CR7">7</CitationRef>, <CitationRef CitationID="CR24">24</CitationRef>]. If <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\alpha (G)+\mu (G)=n(G)-1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>μ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>n</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, then G is a 1-König-Egerváry graph. If G is not a König-Egerváry graph, and there exists a vertex <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$v\in V$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> </mrow> </math></EquationSource> </InlineEquation> (an edge <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$e\in E$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>∈</mo> <mi>E</mi> </mrow> </math></EquationSource> </InlineEquation>) such that <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$G-v$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>v</mi> </mrow> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq10"> <EquationSource Format="TEX">$G-e$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation>) is König-Egerváry, then G is called a vertex (an edge) almost König-Egerváry graph (respectively). For <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$X\subseteq V(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>X</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, the number <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\left| X\right| -\left| N(X)\right| $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <mi>X</mi> </mfenced> <mo>-</mo> <mfenced close="|" open="|"> <mi>N</mi> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mfenced> </mrow> </math></EquationSource> </InlineEquation> is the difference of X, denoted d(X). The critical difference d(G) is <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\max \{d(I):I\in \textrm{Ind}(G)\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>I</mi> <mo stretchy="false">)</mo> <mo>:</mo> <mi>I</mi> <mo>∈</mo> <mtext>Ind</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\textrm{Ind}(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>Ind</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> denotes the family of all independent sets of G. If <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$A\in \textrm{Ind}(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo>∈</mo> <mtext>Ind</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$d\left( A\right) =d(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mfenced close=")" open="("> <mi>A</mi> </mfenced> <mo>=</mo> <mi>d</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, then A is a critical independent set [<CitationRef CitationID="CR25">25</CitationRef>]. Let <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$diadem (G)=\bigcup \{S:S$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mi>i</mi> <mi>a</mi> <mi>d</mi> <mi>e</mi> <mi>m</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>⋃</mo> <mo stretchy="false">{</mo> <mi>S</mi> <mo>:</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> is a critical independent set in <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$G\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> [<CitationRef CitationID="CR8">8</CitationRef>], and <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$\varrho _{v}\left( G\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϱ</mi> <mi>v</mi> </msub> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> denote the number of vertices <InlineEquation ID="IEq20"> <EquationSource Format="TEX">$v\in V\left( G\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, such that <InlineEquation ID="IEq21"> <EquationSource Format="TEX">$G-v$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>v</mi> </mrow> </math></EquationSource> </InlineEquation> is a König-Egerváry graph [<CitationRef CitationID="CR22">22</CitationRef>].In this paper, we characterize all types of almost König-Egerváry graphs and present interrelationships between them. We also show that if G is a 1-König-Egerváry graph, then <InlineEquation ID="IEq22"> <EquationSource Format="TEX">$\varrho _{v}\left( G\right) \le n\left( G\right) +d\left( G\right) -\xi \left( G\right) -\beta (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϱ</mi> <mi>v</mi> </msub> <mfenced close=")" open="("> <mi>G</mi> </mfenced> <mo>≤</mo> <mi>n</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> <mo>+</mo> <mi>d</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> <mo>-</mo> <mi>ξ</mi> <mfenced close=")" open="("> <mi>G</mi> </mfenced> <mo>-</mo> <mi>β</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq23"> <EquationSource Format="TEX">$\beta (G)=\left| diadem (G)\right| $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfenced close="|" open="|"> <mi>d</mi> <mi>i</mi> <mi>a</mi> <mi>d</mi> <mi>e</mi> <mi>m</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. As an application, we characterize the 1-König-Egerváry graphs that become König-Egerváry after deleting any vertex.

On 1-König-Egerváry Graphs

期刊论文
出版模式：

开放获取
发表日期：

2026年2月11日

查看全文

Vadim E. Levit,
Eugen Mandrescu

摘要

Let $\alpha (G)$ $α (G)$ denote the cardinality of a maximum independent set, while $\mu (G)$ $μ (G)$ be the size of a maximum matching in $G=\left( V,E\right) $ $G = (V, E)$ . Let $\xi (G)$ $ξ (G)$ denote the size of the intersection of all maximum independent sets [12]. It is known that if $\alpha (G)+\mu (G)=n(G)=\left| V\right| $ $α (G) + μ (G) = n (G) = |V|$ , then G is a König-Egerváry graph [5, 7, 24]. If $\alpha (G)+\mu (G)=n(G)-1$ $α (G) + μ (G) = n (G) - 1$ , then G is a 1-König-Egerváry graph. If G is not a König-Egerváry graph, and there exists a vertex $v\in V$ $v \in V$ (an edge $e\in E$ $e \in E$ ) such that $G-v$ $G - v$ ( $G-e$ $G - e$ ) is König-Egerváry, then G is called a vertex (an edge) almost König-Egerváry graph (respectively). For $X\subseteq V(G)$ $X \subseteq V (G)$ , the number $\left| X\right| -\left| N(X)\right| $ $|X| - |N (X)|$ is the difference of X, denoted d(X). The critical difference d(G) is $\max \{d(I):I\in \textrm{Ind}(G)\}$ $max {d (I) : I \in Ind (G)}$ , where $\textrm{Ind}(G)$ $Ind (G)$ denotes the family of all independent sets of G. If $A\in \textrm{Ind}(G)$ $A \in Ind (G)$ with $d\left( A\right) =d(G)$ $d (A) = d (G)$ , then A is a critical independent set [25]. Let $diadem (G)=\bigcup \{S:S$ $d i a d e m (G) = ⋃ {S : S$ is a critical independent set in $G\}$ $G}$ [8], and $\varrho _{v}\left( G\right) $ $ϱ_{v} (G)$ denote the number of vertices $v\in V\left( G\right) $ $v \in V (G)$ , such that $G-v$ $G - v$ is a König-Egerváry graph [22].

In this paper, we characterize all types of almost König-Egerváry graphs and present interrelationships between them. We also show that if G is a 1-König-Egerváry graph, then $\varrho _{v}\left( G\right) \le n\left( G\right) +d\left( G\right) -\xi \left( G\right) -\beta (G)$ $ϱ_{v} (G) \leq n (G) + d (G) - ξ (G) - β (G)$ , where $\beta (G)=\left| diadem (G)\right| $ $β (G) = |d i a d e m (G)|$ . As an application, we characterize the 1-König-Egerváry graphs that become König-Egerváry after deleting any vertex.