本文只考虑简单无向图。给定图G=(V, E)和子集X⊆V(G)，G[X]表示由X所导出的子图。将导出子图G[V(G)－X]简记为G－X，对于W⊆E(G)，用G－W来表示删除W中的边后得到的生成子图。Ck和Pk分别表示k个顶点的圈和路，并分别称为k-圈和k-路。对于一个顶点子集S，如果G[S]不含k-路，则称S为图G的一个k-独立集。图的k-独立数αk(G)定义为图中最大k-独立集的阶数，特别地，α2(G)正是被广泛研究的独立数，因此k-独立数是独立数的一个自然推广，3-独立数在文献中往往被称为分离数。图G的k-路匹配是指一个k-路集合，其中任意两个k-路之间是点不交的，2-路匹配即为经典的匹配。称k-路匹配Mk的阶数为集合Mk中元素的数目，即Mk中k-路的数目，定义图G的k-路匹配数μk(G)为最大k-路匹配的阶数。
给定图G=(V, E)和正整数k≥2，最小顶点覆盖k-路问题(MVCPk)是在图G中找一个最小顶点子集F，使得图G中的任何一条k-路都至少有一个顶点在F中。如果一个顶点子集F是MVCPk的一个可行解，则称F为一个顶点覆盖k-路集合(VCPk集)，图G的顶点覆盖k-路数τk(G)被定义为图中最小VCPk集的阶数。顶点覆盖k-路问题的提出源于多个实际应用问题，如无线传感器网络加密以及交通摄像头安装问题[1]等，当k为2时，MVCPk正是著名的顶点覆盖问题，因此它是顶点覆盖问题的一个自然的推广。
由αk(G)和μk(G)的定义易知，对于一般图G和正整数k≥2，有αk(G)+μk(G)≤|V(G)|。但根据König-Egerváry定理，对于任意的二部图G，有α2(G)+μ2(G)=|V(G)|。因为二部图的匹配数可以在多项式时间内求出，因此根据König-Egerváry定理，二部图的独立数也可以在多项式时间内求出。又因为对任意图都有αk(G)+τk(G)=|V(G)|，因此对于二部图，顶点覆盖数也能在多项式时间内求出。但α2(G)+μ2(G)=|V(G)|并不只在二部图上成立，由此，研究者给出了König-Egerváry图的定义[2-3]：一个图G如果满足α2(G)+μ2(G)=|V(G)|，则称图G为一个König-Egerváry图。近几十年来，学者们从禁用子图、算法设计、谱等方面对König-Egerváry图作了深入研究[4-7]，因此将König-Egerváry图的概念进行推广，并对k-路形式的König-Egerváry图进行研究是十分必要的。
本文首先考虑了树，证明树都是k-路形式的König-Egerváry图；其次考虑了单圈图，研究发现并非所有的单圈图都是k-路形式的König-Egerváry图，但这些单圈图都具有一些特定性质。
1 树本文推广了König-Egerváry图的概念，给出了如下定义。
定义1 对于正整数k≥2，一个图G如果满足αk(G)+μk(G)=|V(G)|，则认为图G满足k-路形式的König-Egerváry性质，称它为一个k-路形式的König-Egerváry图。
因为对任意图G，都有αk(G)+τk(G)=|V(G)|，所以不难得出，一个图G是k-路形式的König-Egerváry图当且仅当μk(G)=τk(G)。此处考虑树的情况，证明树都是k-路形式的König-Egerváry图。
定理1 对于任意的树，T是k-路形式的König-Egerváry图。
证明：对树的顶点数|V(T)|进行归纳。
当|V(T)|≤k－1时，显然有μk(T)=τk(T)=0，即T是k-路形式的König-Egerváry图。
假设|V(T)|≤n时T是k-路形式的König-Egerváry图，现考虑|V(T)|=n+1时的树T。任选T中的一个顶点r，将T变成以r为根的根树，对于T上每个顶点v，其层数l(v)为T中从顶点r到顶点v的通路长度。
用Tu表示以u为根的子树，找到包含k-路且根u的层数最大的子树Tu，这种子树显然存在。易知μk(Tu)=1，且Tu上的任意一条k-路必通过顶点u，否则与u的层数最大相矛盾。
令T′=T\Tu，假设F为T的一个最小k-路顶点覆盖集，则F∩V(Tu)≠Ø，且F′=(F\V(Tu))∪{u}也为T的最小k-路顶点覆盖集，F′\{u}为T′的一个k-路顶点覆盖集，因此有τk(T′)≤τk(T)－1；另一方面，若F″为T′的一个最小k-路顶点覆盖集，则F″∪{u}为T的一个最小k-路顶点覆盖集，因此有τk(T)≤τk(T′)+1。综上，有τk(T)=τk(T′)+1。
令M为T的一个k-路匹配，设Q为Tu中的一条k-路，则可通过替换得到一个k-路匹配M′，并使得M′中含有Q，此时M′\{Q}为T′的一个k-路匹配，故有μk(T′)≥μk(T)－1；另一方面，如果M″为T′的一个k-路匹配，则M″∪{Q}为T的一个k-路匹配，故有μk(T)≥μk(T′)+1。由此有μk(T)=μk(T′)+1。
由归纳假设可知T′是k-路形式的König-Egerváry图，即μk(T′)=τk(T′)，所以有τk(T)=μk(T)，由此证明任何一个树都是k-路形式的König-Egerváry图。定理1得证。
显然，可以很容易地由定理1得到推论1。
推论1 森林是k-路形式的König-Egerváry图。
2 单圈图若一个简单连通图G=(V, E)满足|V(G)|=|E(G)|，则称图G是一个单圈图。对简单图G，用Ωk(G)表示集族{S:S是G的最大k-路独立集}，用corek(G)表示G的最大k-独立集的核，即G的所有最大k-独立集的交集所构成的集合，则有corek(G)=∩{S:S∈Ωk(G)}。
如果αk(G－e)>αk(G)，则称边e是αk-临界边；如果μk(G－e)＜μk(G)，则称e是μk-临界边。
下面给出一些关于临界边的结构定理。
引理1 令G是一个图，e是G的一条边，如果e是G的一条αk-临界边，则αk(G－e)=αk(G)+1；如果e是G的一条μk-临界边，则μk(G－e)=μk(G)-1。
证明：(1)设e是G的一条αk-临界边，F为G－e的一个最大k-独立集，e的两个端点为v和w。假设v∉F或u∉F，易知F也是G的一个k-独立集，故有αk(G－e)≤αk(G)，这与e是G的一条αk-临界边相矛盾，因此v∈F且u∈F；另一方面，因F－u是G的一个k-独立集，因此αk(G－e)≤αk(G)+1。综上有αk(G－e)=αk(G)+1。
(2) 类似地，设e是G的一条μk-临界边，因为删掉一条边e后μk(G－e)≥μk(G)-1；又因为e是μk-临界边，由μk-临界边的定义可知，μk(G－e)≤μk(G)+1。因此有μk(G－e)=μk(G)－1。引理1得证。
引理2 对任意图G，corek(G)中没有αk-临界边的端点。
证明：令uv为G的一条αk-临界边，F是G－uv的最大k-独立集。由引理1知u∈F且v∈F，易知F－u和F－v都是G的最大k-独立集，因此有corek(G)⊆F\{u, v}，即corek(G)中没有αk-临界边的端点。引理2得证。
进一步考虑n阶单圈图。
引理3 若G是一个n阶单圈图，那么有n－1≤αk(G)+μk(G)≤n。
证明：记图中的圈为C，找到一条边e=xy∈E(C)，使得G－e是树。由定理1知，所有的树都是k-路形式的König-Egerváry图，因此有αk(G－e)+μk(G－e)=n；又因为αk(G－e)≤αk(G)+1且μk(G－e)≤μk(G)，所以有αk(G－e)+μk(G－e)≤αk(G)+μk(G)+1，即n－1≤αk(G)+μk(G)≤n。引理3得证。
定理2 若图G是n阶单圈图，则α3(G)+μ3(G)=n－1当且仅当唯一的圈C上每条边都是α3-临界的。
证明：首先证明必要性。对于任意的e∈E(C)，若G－e是树，则有α3(G－e)+μ3(G－e)=n；又因为α3(G)+μ3(G)=n－1且μ3(G－e)≤μ3(G)，所以有α3(G－e)≥α3(G)+1。故e是α3-临界的，从而圈上每条边都是α3-临界的。
然后证明充分性。假设圈C上每条边都是α3-临界的，因为所有μ3-临界边都被每个最大3-路匹配所包含，所以不可能存在一条4路，其路上的所有边全是μ3-临界的；同理，一个三角形的3条边不可能都是μ3-临界的。因此存在e∈E(C)，使得
| $ {\mu _3}\left( {G - e} \right) = {\mu _3}\left( G \right) $ | (1) |
由G－e是树，有
| $ {\alpha _3}\left( {G - e} \right) + {\mu _3}\left( {G - e} \right) = n $ | (2) |
因为C上每条边都是α3-临界的，故有
| $ {\alpha _3}\left( G \right) + 1 = {\alpha _3}\left( {G - e} \right) $ | (3) |
综合式(1)~(3)可得α3(G)+μ3(G)=n－1。定理2得证。
图G顶点v∈V(G)的邻域是集合N(v)={w:w∈V(G)且vw∈E(G)}，因此对顶点集A，其邻域为N(A)=∪{N(v):v∈A}。设y为圈C的一个顶点，xy为图的一条不在圈上的边，令Tx是G－xy中包含顶点x的树。
对于不满足3-路形式König-Egerváry性质的单圈图，下文研究它们分离集的核的结构。
推论2 若G是不满足3-路形式König-Egerváry性质的单圈图，那么圈上的点都不在core3(G)中。
证明：由引理2和定理2即可得到推论1。通过推论1可知，不满足3-路形式König-Egerváry性质的单圈图，其圈上的顶点不在分离集的核中，因此只需考虑圈以外的顶点。
定理3 若G是不满足3-路形式König-Egerváry性质的单圈图，其中唯一的圈为C=(V(C), E(C))，那么core3(G)=∪{core3(Tx):x∈N(V(C))\V(C)}。
证明：设y为圈C的一个顶点，xy为图的一条不在圈上的边，则x∈N(V(C))\V(C)。设z是y在圈中的一个邻点，由定理2知yz是α3临界的，因此存在一个图的最大分离集Sy∈Ω3(G)使得y∈Sy；同理，存在Syz∈Ω3(G－yz)使得{y, z}⊂Syz。
先给出两个断言，然后通过这两个断言来证明定理3。
断言1：每个Tx的最大分离集可以扩展到一个G的最大分离集。
证明：设A∈Ω3(Tx)是Tx的一个最大分离集，分x∉A和x∈A两种情况来讨论。
(1) x∉A
若x∉Sy，由Sy\V(Tx)是G－Tx的分离集有|Sy\V(Tx)|≤α3(G－Tx)。首先证明|Sy\V(Tx)|=α3(G－Tx)。若|Sy\V(Tx)|＜α3(G－Tx)，设S0为G－Tx的一个最大分离集，则S1=S0∪(Sy∩V(Tx))是G的分离集，且|S1|>α3(G)，这与S1是G的分离集相矛盾，因此有|Sy\V(Tx)|=α3(G－Tx)。其次证明W=A∪(Sy\V(Tx))∈Ω3(G)。因为x∉A且x∉Sy，因此W是G的分离集，又因为α3(G)≤α3(G－Tx)+α3(Tx)=|Sy\V(Tx)|+|A|，所以有W=A∪(Sy\V(Tx))∈Ω3(G)。x∉A且x∉Sy的情况得证。
若x∈Sy，由Sy∩V(Tx)是Tx的分离集，有|A|≥|Sy∩V(Tx)|；由x∉A，有G=(Sy\(Sy∩V(Tx)))∪A是G的分离集；又因为|W|≥α3(G)，所以W为G的最大分离集，因此有A⊆W∈Ω3(G)。x∉A且x∈Sy的情况得证。
情况(1)得证。
(2) x∈A
因为Syz∩V(Tx)是Tx的分离集，所以有|A|≥|Syz∩V(Tx)|，由yz是α3临界边可得α3(G)=|Syz\{y}|。又因为W=(Syz\{y}\(Syz∩V(Tx)))∪A是一个G的分离集，且α3(G)=|Syz\{y}|≤|W|，因此W为G最大分离集，进而有A⊆W∈Ω3(G)。
综合情况(1)、(2)可得，每个Tx的最大分离集都可以扩展到一个G的最大分离集。断言1得证。
断言2：对任意的S∈Ω3(G)和x∈N(V(C))\V(C)，都有S∩V(Tx)∈Ω3(Tx)。
证明：分y∉S以及y∈S两种情况进行讨论。
(1) y∉S
令B=S∩V(Tx)，用反证法证明B∈Ω3(Tx)。假设B=S∩V(Tx)∉Ω3(Tx), 则存在A∈Ω3(Tx)使得H=(S\B)∪A为G分离集；又因为|H|>α3(G)，与H=(S\B)∪A为G分离集相矛盾，因此有B∈Ω3(Tx)。
(2) y∈S
令B=S∩V(Tx)，易知G－Tx为不满足3-路形式König-Egerváry性质的单圈图；又由e=yz是α3临界边，有α3(G－Tx－e)=α3(G－Tx)+1，由引理1知存在G－Tx－e的最大分离集S′yz，使得{y, z}⊂S′yz，易知S′yz\{y}为G－Tx的最大分离集。将S∩V(G－Tx)替换为S′yz\{y}，则(S′yz\{y})∪B仍为G上分离集；又因为|S′yz\{y}|≥|S∩V(G－Tx)|，所以(S′yz\{y})∪B为G最大分离集。
用反证法证明B∈Ω3(Tx)。假设B∉Ω3(Tx)，则存在A∈Ω3(Tx)使得(S′yz\{y})∪A为G分离集，因为(S′yz\{y})∪A的阶数大于α3(G)，这与(S′yz\{y})∪A是G的分离集相矛盾，因此B∈Ω3(Tx)。
由情况(1)、(2)可知，对任意的S∈Ω3(G)和x∈N(V(C))\V(C)，都有S∩V(Tx)∈Ω3(Tx)。断言2得证。
由断言1和断言2有
core3(Tx)=∩{A:A∈Ω3(Tx)}=∩{S∩V(Tx):S∈Ω3(G)}=(∩{S:S∈Ω3(G)})∩V(Tx)=core3(G)∩V(Tx)
故有core3(G)=∪{core3(Tx):x∈N(V(C))\V(C)}。
定理3得证。
3 结束语本文提出了k-路形式的König-Egerváry图，并证明了树是k-路形式的König-Egerváry图。进一步考虑了单圈图，并给出了不满足3-路形式的König-Egerváry性质的单圈图的等价条件，以及这些图分离集核的结构。
| [1] |
TU J H, ZHOU W L. A primal-dual approximation algorithm for the vertex cover P3 problem[J]. Theoretical Computer Science, 2011, 412(50): 7044-7048. DOI:10.1016/j.tcs.2011.09.013 |
| [2] |
ROBERT W D. Independence numbers of graphs-an extension of the König-Egerváry theorem[J]. Discrete Mathematics, 1979, 27: 23-33. DOI:10.1016/0012-365X(79)90066-9 |
| [3] |
STERBOUL F. A characterization of the graphs in which the transversal number equals the matching number[J]. Journal of Combinatorial Theory, Series B, 1979, 27: 228-229. DOI:10.1016/0095-8956(79)90085-6 |
| [4] |
BONOMO F, DOURADO M C, DURAN G, et al. Forbidden subgraphs and the König-Egerváry property[J]. Discrete Applied Mathematics, 2013, 161: 2380-2388. DOI:10.1016/j.dam.2013.04.020 |
| [5] |
LARASON C E. The critical independence number and an independence decomposition[J]. European Journal of Combinatorics, 2011, 32: 294-300. DOI:10.1016/j.ejc.2010.10.004 |
| [6] |
MOSCA R, NOBILI P. Polynomial time recognition of essential graphs having stability number equal to matching number[J]. Graphs and Combinatorics, 2015, 31: 1649-1658. DOI:10.1007/s00373-014-1483-4 |
| [7] |
BOURJOLLY J M, PULLEYBLANK W R. König-Egerváry graphs, 2-bicritical graphs and fractional matchings[J]. Discrete Applied Mathematics, 1989, 24: 63-82. DOI:10.1016/0166-218X(92)90273-D |