最大度至多为3的图上极大分离集的最大数目

引用本文

李雨欣, 苏贵福. 最大度至多为3的图上极大分离集的最大数目[J]. 北京化工大学学报(自然科学版), 2022, 49(3): 102-107. DOI: 10.13543/j.bhxbzr.2022.03.014.

LI YuXin, SU GuiFu. On the maximum number of maximal dissociation sets in graphs with maximum degree at most three[J]. Journal of Beijing University of Chemical Technology (Natural Science), 2022, 49(3): 102-107. DOI: 10.13543/j.bhxbzr.2022.03.014.

基金项目

北京市自然科学基金面上项目(1222012)

第一作者

李雨欣, 女, 1997年生, 硕士生.

通信联系人

苏贵福, E-mail：gfs@mail.buct.edu.cn

文章历史

收稿日期：2021-09-01

Contents

Abstract

Full text

Figures/Tables

PDF

最大度至多为3的图上极大分离集的最大数目

李雨欣 , 苏贵福

北京化工大学数理学院，北京 100029

收稿日期：2021-09-01

基金项目：北京市自然科学基金面上项目(1222012)

第一作者：李雨欣, 女, 1997年生, 硕士生

通信联系人：苏贵福, E-mail：gfs@mail.buct.edu.cn

摘要：给定图G=(V, E), 若顶点子集F在图G中的导出子图的最大度至多为1, 则称F为图G的一个分离集；若F不是其他分离集的真子集, 则称F为一个极大分离集。对极大分离集计数问题进行研究, 证明了在所有n个顶点且最大度至多为3的图上最多有$ {6^{\frac{\mathit{n}}{{\rm{4}}}}}$个极大分离集, 并刻画了相应的极图结构。

关键词：最大度为3的图分离集极大分离集

On the maximum number of maximal dissociation sets in graphs with maximum degree at most three

LI YuXin , SU GuiFu

College of Mathematics and Physics, Beijing University of Chemical Technology, Beijing 100029, China

Abstract: A subset of vertices F in a graph G is a dissociation set if the induced subgraph G[F] has maximum degree at most one. If F is not a proper subset of any other dissociation sets, then F is a maximal dissociation set of G. Obviously, the dissociation set is a natural generalization of the independent set. In this paper, the counting problem of maximal dissociation sets is considered. We show that there are at most $ {6^{\frac{\mathit{n}}{{\rm{4}}}}}$ maximal dissociation sets in n-vertex graphs with maximum degree at most three. The extremal graphs achieving the maximum value have also been completely characterized.

Key words: graphs of maximum degree at most three dissociation set maximal dissociation set

引言

若图G中每个顶点的度都为r, 则称图G为r-正则图。用S_n、P_n、C_n和K_n分别表示n个顶点的星图、路、圈和完全图, K_{m, n}表示完全二部图, 其中二部划分为(X, Y), 且|X|=m，|Y|=n。对于两个图G和H, 若V(G)∩V(H)=Ø, 则称G与H不相交。两个不相交的图G和H的并记为G∪H, 而nG表示n个G的不交并。

对于图G的顶点子集$ \mathit{F} \subseteq \mathit{VG}$, 用G[F]表示F在图G中的导出子图, 用G- F表示导出子图G[V\F]。方便起见, 将G- {v}简记为G- v。图G的最大度和最小度分别用Δ(G)和δ(G)表示, 简记为Δ和δ。设顶点u, v∈V(G), 用u~v表示顶点u和v相邻，$ u v表示顶点u和v不相邻。用N_G(v)和N_G[v]分别表示顶点v在图G中的开邻域和闭邻域，简记为N(v)和N[v]。顶点v在图G中的度记为d_G(v), 简记为d(v)，若d(v)=1, 则称顶点v为图G的悬挂点。

在图G中, 若顶点子集S的导出子图的最大度等于0, 则称S为图G的一个独立集；若S不为其他独立集的真子集, 则称S为一个极大独立集。图中包含顶点个数最多的独立集称为最大独立集。在20世纪60年代Moser等^[1]提出如下计数问题：n个顶点的一般图上极大独立集的最大数目是多少？相应的极图又是什么？随后在文献[1]中他们证明了对于n个顶点的图G，其极大独立集个数至多为3^n/3个，当n≡0(mod 3)且G为n/3个K₃的不交并时达到极值；对于其他的n值，他们也给出了精确的极值并刻画了极图。

此后, 学者们聚焦于不同图类上的极大独立集和最大独立集的计数问题的研究，特别是在连通图^[2-3]、无三角形的图^[4]、二部图^[5]、单圈图^[6]和最多含有r个圈的图^[7]等方面获得重要结果。由于图子结构同社团结构间的关系密切，研究其他图子结构的计数问题也具有重要意义，因此学者们将计数对象扩展得到其他极值结果，如最小支配集^[8-9]、极小支配集^[10]、最小连通点覆盖^[11]、最小反馈点集^[12]以及极小反馈点集^[13]等图子结构。图子结构的计数问题成为图论和组合数学领域的一个研究热点。

给定图G=(V, E), 若顶点子集F在G中的导出子图的最大度至多为1, 则称F为图G的一个分离集；若F不为其他分离集的真子集, 则称F为一个极大分离集。图中包含顶点个数最多的分离集称为最大分离集。显然图的独立集同时也是其分离集。1981年Yannakakis^[14]首次提出分离集的概念, 并证明了最大分离集问题在二部图上是N P- 困难的。近几十年来, 学者们对不同图类上的最大分离集问题的计算复杂性作了深入研究, 详见文献[15-16]。

本课题组前期对最大分离集的计数问题进行研究^[17], 得到了所有n阶树上最大分离集的最大数目, 并刻画了极图结构。后续又针对一般图、无三角图等特殊图类也进行了研究^[18]，通过进一步分析，可直接得到最大度至少为3的图上极大分离集的极值结果。因此，本文考虑了最大度为3的图上极大分离集的计数问题, 证明了在所有n个顶点且最大度至多为3的图上最多有$ {6^{\frac{\mathit{n}}{{\rm{4}}}}}{\rm{ }}$个极大分离集, 并刻画了相应的极图。

1 相关引理

用MD(G)表示图G中所有极大分离集构成的集合, 并记ϕ(G)=|MD(G)|。

为方便后续讨论, 令$ \mathit{a }{\rm{ = }}{6^{\frac{{\rm{1}}}{{\rm{4}}}}}$, 并对图G中的极大分离集进行如下划分：ϕ(G, v)=|{F|F∈MD(G)且v∉F}|, ϕ(G, v⁰)=|{F|F∈MD(G), v∈F且d_G[F](v)=0}|, ϕ(G, v¹)=|{F|F∈MD(G), v∈F且d_G[F](v)=1}|。下面的引理1显然成立。

引理1 对于两个不相交的图G和H, 有

$ \phi \left( {G \cup H} \right) = \phi \left( G \right)\cdot\phi \left( H \right)$

引理2 设v是任意图G中的顶点, 有

$ \phi \left( G \right) \le \phi \left( {G - v} \right) + \phi \left( {G - N\left[ v \right]} \right) + \sum\limits_{u \in N\left( v \right)} {\phi \left( {G - {\rm{ }}N\left[ v \right] \cup N\left[ u \right]} \right)} $

若存在顶点w∈N(v)使得N[w]⊆N[v], 则

$ \phi \left( G \right) \le \phi \left( {G - v} \right) + \sum\limits_{u \in N\left( v \right)} {\phi \left( {G - {\rm{ }}N\left[ v \right] \cup N\left[ u \right]} \right)} $

证明：对图G中的极大分离集进行划分, 有

$ \begin{array}{l} \phi \left( G \right) = \phi \left( {G, \bar v} \right) + \phi (G, {v^0}) + \phi (G, {v^1}) \le \phi \left( {G - {\rm{ }}v} \right) + \phi \left( {G - N\left[ v \right]} \right) + \end{array}$ $ \begin{array}{l} \sum\limits_{u \in N\left( v \right)} {\phi \left( {G - N\left[ v \right] \cup N\left[ u \right]} \right)} \end{array}$

若存在顶点w∈N(v)使得N[w]⊆N[v], 则$ \phi (G, {v^0}) = 0$。因此

$ \begin{array}{l} \phi \left( G \right) = \phi \left( {G, \bar v} \right) + \phi (G, {v^0}) + \phi (G, {v^1}) \le \phi \left( {G - {\rm{ }}v} \right) + \end{array}$ $ \begin{array}{l} \sum\limits_{u \in N\left( v \right)} {\phi \left( {G - N\left[ v \right] \cup N\left[ u \right]} \right)} \end{array}$

引理3 设v是图G中的一悬挂点, w是其邻点, 则

$ \phi \left( G \right) \le \sum\limits_{u \in N\left( w \right)/\left\{ v \right\}} {\phi \left( {G - N\left[ w \right] \cup N\left[ u \right]} \right) + \phi \left( {G - {\rm{ }}v - w} \right) + \phi \left( {G - N\left[ w \right]} \right)} $

证明：若在图G中存在极大分离集F, 使得悬挂点v∈F, 则顶点w∈F且d_G[F](w)=1。因此

$ \begin{array}{l} \phi \left( G \right) = \phi \left( {G, \bar v} \right) + \phi (G, {v^0}) + \phi (G, {v^1}) \le \end{array}$ $ \begin{array}{l} \sum\limits_{u \in N\left( w \right)/\left\{ v \right\}} {\phi \left( {G - N\left[ w \right] \cup N\left[ u \right]} \right) + \phi \left( {G - {\rm{ }}v - w} \right) + \phi \left( {G - N\left[ w \right]} \right)} \end{array}$

引理4 若图G中有一顶点w恰与两个悬挂点v₁和v₂相邻, 则

$ \begin{array}{l} \phi \left( G \right) \le \sum\limits_{u \in N\left( w \right)/\left\{ {{v_1}, {v_2}} \right\}} {\phi \left( {G - N\left[ w \right] \cup N\left[ u \right]} \right) + } \phi (G - \{ w, {v_1}, {v_2}\} ) + 2\phi \left( {G - N\left[ w \right]} \right) \end{array}$

证明：图G中极大分离集所构成的集合可分为以下3类：不包含v₁和v₂；包含v₁和v₂；包含v₁和w或包含v₂和w。因此

引理5 设P_n是含有n个顶点的路, 则$ \phi ({P_n})<{\rm{0}}.{\rm{81}}{\mathit{a}^\mathit{n}}$。

证明：对顶点数n作归纳。当n≤4时, 易验证结论成立。因此, 在后续讨论中总假设n≥5, 且对任意的P_n-1结论均成立。设顶点v为P_n的悬挂点, w是其邻点，而u是w的另一邻点。由归纳假设及引理3, 有

$ \begin{array}{l} \phi ({P_n}) < \phi ({P_{n - 4}}) + \phi ({P_{n - 2}}) + \phi ({P_{n - 3}}) < 0.81{a^{n - 4}} + 0.81{a^{n - 2}} + \end{array}$ $ \begin{array}{l} 0.81{a^{n - 3}} = 0.81{a^n}({a^{ - 2}} + {a^{ - 3}} + {\rm{ }} {a^{ - 4}}) < 0.81{a^n} \end{array}$

引理6 设C_n是含有n个顶点的圈, 则$ \phi ({C_n}) \le {a^n}$, 等号成立当且仅当n=4。

证明：当n=3或n=4时, 易验证结论成立。因此, 后续讨论中假设n≥5。根据引理2和引理5, 有

$ \begin{array}{l} \phi ({C_n}) < \phi ({P_{n - 1}}) + \phi ({P_{n - 3}}) + 2\phi ({P_{n - 4}}) < 0.81{a^{n - 1}} + 0.81{a^{n - 3}} + \end{array}$ $ \begin{array}{l} 2 \times 0.81{a^{n - 4}} = 0.81{a^n}({a^{ - 1}} + {a^{ - 3}} + 2{a^{ - 4}}) < 0.81{a^n} \end{array}$

2 主要结论及证明 2.1 主要结论

本节研究n个顶点且最大度至多为3的图中极大分离集的最大个数, 得到如下主要定理。

定理1 设G是任一n阶图, 且其最大度Δ≤3, 则$ \phi (G) \le {6^{\frac{{\rm{n}}}{4}}}$, 等号成立当且仅当n≡0(mod 4)且图G同构于

$ \left\{ {\begin{array}{*{20}{l}} {\frac{\mathit{n}}{4}{C_4},}&{\Delta = 2}\\ {a{C_4} \cup b{H_4} \cup c{K_4},}&{\Delta = 3\;\;\delta = 2}\\ {\frac{\mathit{n}}{4}{K_4},}&{\Delta = \delta = 3} \end{array}} \right.$

其中H₄为K₄删去1条边后所得到的图, 而a、b、c为非负整数且a+b+c= $ {\frac{{\rm{n}}}{4}}$。

2.2 定理1的证明

对顶点个数n作归纳。当n < 6时, 易验证结论成立。因此, 在后续讨论中假设n≥6, 且对于任意最大度至多为3的n-1阶图结论均成立。

当图G不连通时, 设G₁和G₂是G的两个连通分支, 且|V(G)|=|V(G₁)|+|V(G₂)|=n₁+n₂。显然G₁和G₂皆为最大度至多为3的图, 根据归纳假设及引理1, 有

$ \phi \left( G \right) = \phi ({G_1})\cdot\phi ({G_2}) \le {a^{{n_1}}}\cdot{a^{{n_2}}} = {a^n} $

等号成立当且仅当G₁和G₂同时满足定理中的极图结构, 亦即图G满足定理中的极图结构。

接下来考虑图G为连通图的情形。为方便后续证明, 给出以下两个断言。

断言1 若连通图G包含悬挂点v, 则ϕ(G) < aⁿ。

证明：记v的邻点为w。由归纳假设及引理4, 有

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( G \right) \le \left( {d\left( w \right) - 1} \right){a^{n - d\left( w \right) - 1}} + {a^{n - 2}} + {a^{n - d\left( w \right) - 1}} = \\ {a^n}(d\left( w \right){a^{ - d\left( w \right) - 1}} + {a^{ - 2}}) \end{array} $

注意到n≥6且Δ≤3, 则有d(w)∈{2, 3}。经计算可得ϕ(G) < aⁿ。

断言2 若连通图G中存在顶点u使得N(u)= {v, w}, 且d(w)=3, d(v)=2, 则ϕ(G) < aⁿ。

证明：设N(v)={u, t}。当t=w时, 有N[u]⊆N[w], 故图$ G - w \cong uv \cup \left( {G - \{ u, v, w\} } \right)$。由归纳假设知

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( G \right) \le {a^{n - 3}} + 2{a^{n - 4}} + {a^{n - 5}} = {a^n}({a^{ - 3}} + 2{a^{ - 4}} + \\ {a^{ - 5}})<{a^n} \end{array} $

当t≠w时, 分以下两种情况讨论。

情况1 t∈N(w), N(w)={u, t, s}

当d(t)=2时, 图$ G - w \cong {P_3} \cup \left( {G - \{ w, u, v, t\} } \right)$, 则由归纳假设知

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( G \right) \le 3{a^{n - 4}} + {a^{n - 4}} + 3{a^{n - 5}} = {a^n}(4{a^{ - 4}} + 3{a^{ - 5}})<\\ {a^n} \end{array} $

当d(t)=3时, 如果s∈N(t)且d(s)=2, 则V(G)={u, v, w, t, s}, 易得ϕ(G)=6 < a⁵。否则, 图G-w包含悬挂点u, 且d_G-w(t)=2, 这就说明图$ G - N\left[ w \right] \cong v \cup \left( {G - \{ u, v, w, t, s\} } \right)$。因此, 有

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( {G - w} \right) \le {a^{n - 5}} + {a^{n - 3}} + {a^{n - 4}}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - w} \right) + {a^{n - 5}} + 3{a^{n - 5}} \le {a^n}({a^{ - 3}} + {a^{ - 4}} + \\ 5{a^{ - 5}})<{a^n} \end{array} $

情况2 t∉N(w), N(w)={u, s₁, s₂}

当d(s₁)=2且N[s₁]={w, s₁, s₂}⊆N[w]时, 图G-w包含悬挂点u, 于是由归纳假设得

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( {G - w} \right) \le {a^{n - 5}} + {a^{n - 3}} + {a^{n - 4}}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - w} \right) + {a^{n - 4}} + 2{a^{n - 5}} \le {a^n}({a^{ - 3}} + \\ 2{a^{ - 4}} + 3{a^{ - 5}})<{a^n} \end{array} $

否则, 设A=N(t)-{v, s₁, s₂}。当A=Ø时, 图G-w中包含悬挂点u, 此时容易发现图$ G - N\left[ w \right] \cong {\rm{ }}vt \cup (G - \{ u, v, w, t, {s_1}, {s_2}\} )$。因此

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( {G - w} \right) \le {a^{n - 5}} + {a^{n - 3}} + {a^{n - 4}}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - w} \right) + {a^{n - 6}} + 3{a^{n - 5}} \le {a^n}({a^{ - 3}} + {a^{ - 4}} + \\ 4{a^{ - 5}} + {a^{ - 6}})<{a^n} \end{array} $

当A≠Ø时, 有1≤|A|≤2。对于v_i∈A, 记B_i= N(v_i)-{t, s₁, s₂}, 其中1≤i≤2。若对于任意B_i都有B_i=Ø, 则图G-w包含悬挂点u, 且

$ G - N\left[ w \right] \cong {P_3} \cup (G - \{ u, v, w, t, {s_1}, {s_2}, {v_1}\} ) $

或

$ G - N\left[ w \right] \cong {S_4} \cup (G - \{ u, v, w, t, {s_1}, {s_2}, {v_1}, {v_2}\} ) $

于是, 由归纳假设知

$ \begin{array}{l} \;\;\;\;\;\phi \left( {G - w} \right) \le {a^{n - 5}} + {a^{n - 3}} + {a^{n - 4}}\\ \;\;\;\;\;\phi \left( {G - N\left[ w \right]} \right) \le {\rm{max}}\{ 3{a^{n - 7}}, 4{a^{n - 8}}\} = 3{a^{n - 7}}\\ \;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - w} \right) + \phi \left( {G - N\left[ w \right]} \right) + 3{a^{n - 5}} \le {a^n}\\ ({a^{ - 3}} + {a^{ - 4}} + 4{a^{5}} + 3{a^{7}})<{a^n} \end{array} $

若存在B_i使得B_i≠Ø, 则图G-w包含悬挂点u, 图G-N[w]包含悬挂点v。因此

$ \begin{array}{l} \;\;\;\;\;\;\phi \left( {G - w} \right) \le {a^{n - 5}} + {a^{n - 3}} + {a^{n - 4}}\\ \;\;\;\;\;\;\phi \left( {G - N\left[ w \right]} \right) \le {\rm{max}}\{ {a^{n - 9}} + {a^{n - 7}} + 2{a^{n - 8}}, {a^{n - 8}} + \\ {a^{n - 6}} + {a^{n - 7}}, 2{a^{n - 9}} + {a^{n - 6}} + {a^{n - 8}}\} = {a^{n - 8}} + {a^{n - 6}} + {a^{n - 7}}\\ \;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - w} \right) + \phi \left( {G - N\left[ w \right]} \right) + 3{a^{n - 5}} \le {a^n}\\ ({a^{ - 3}} + {a^{ - 4}} + 4{a^{ - 5}} + {a^{ - 6}} + {a^{ - 7}} + {a^{ - 8}})<{a^n} \end{array} $

综上, 断言2得证。

由断言1可知, 当δ=1时, 有ϕ(G) < aⁿ。由引理6可知, 若Δ=δ=2, 则ϕ(G)≤aⁿ。因此, 接下来只需研究Δ=3且δ=2的图以及3-正则图。

情形Ⅰ Δ=3且δ=2

在这种情形下, 图中必有一个三度顶点v和二度顶点u相邻。设N(u)={v, t}, N(v)={u, v₁, v₂}。由断言2可知, 当d(t)=2时, 有ϕ(G) < aⁿ。因此, 在后续讨论中总假设d(t)=3。

当t=v₁时, 有N[u]⊆N[v]。若d(v₂)=2且v₁~v₂, 则图V(G)={v, u, v₁, v₂}且ϕ(G)=6=a⁴。否则, 图G-v包含悬挂点u, 于是由归纳假设得

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( {G - v} \right) \le {a^{n - 5}} + {a^{n - 3}} + {a^{n - 4}}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - v} \right) + 2{a^{n - 4}} + {a^{n - 5}} \le {a^n}({a^{ - 3}} + \\ 3{a^{ - 4}} + 2{a^{ - 5}})<{a^n} \end{array} $

当t≠v₁时, 若N(t)={u, v₁, v₂}且v₁和v₂都是二度顶点, 则图$ G \cong {K_{2, 3}}$。因此, ϕ(G)=8 < a⁵。否则, 图G-v包含悬挂点u。进一步地, 设$ {E_1} = \sum\limits_{z \in N\left( v \right)} {\phi \left( {G - N\left[ v \right] \cup N\left[ z \right]} \right)} , $由归纳假设知

$ \begin{array}{l} \;\;\;\;\;\;\phi \left( {G - v} \right) \le {\rm{max}}\{ {a^{n - 6}} + {a^{n - 4}} + 2{a^{n - 5}}, 2{a^{n - 6}} + \\ {a^{n - 3}} + {a^{n - 5}}\} = 2{a^{n - 6}} + {a^{n - 3}} + {a^{n - 5}}\\ \;\;\;\;\;\;{E_1} \le {\rm{max}}\{ {a^{n - 6}} + 2{a^{n - 5}}, {a^{n - 5}} + 2{a^{n - 6}}, 3{a^{n - 5}}\} = \\ 3{a^{n - 5}}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - v} \right) + {a^{n - 4}} + {E_1} \le {a^n}({a^{ - 3}} + {a^{ - 4}} + \\ 4{a^{ - 5}} + 2{a^{ - 6}})<{a^n} \end{array} $

情形Ⅱ 3-正则图

若G为一n阶3-正则连通图, 分两种情况进行讨论。

情况1 图G中不含C₃

设v为图G的一个顶点, N(v)={v₁, v₂, v₃}且N(v₂)={v, s, t}, 如图 1所示。

图 1 图G中不含C₃ Fig.1 Case where G doesn't contain C₃

若N(s)=N(t)={v₁, v₂, v₃}, 则$ G \cong {K_{3, 3}}$, 进而ϕ(G)=11 < a⁶。

若N(s)∩{v₁, v₃}=Ø且|N(t)∩N(s)|=3, 即图G具有图 2所示子结构, 由归纳假设有

$ \begin{array}{l} \;\;\;\;\;\;\phi \left( {G - v - s} \right) \le 2{a^{n - 7}} + {a^{n - 4}} + {a^{n - 6}}\\ \;\;\;\;\;\;\phi \left( {G - v} \right) \le \phi \left( {G - v - s} \right) + {a^{n - 5}} + {a^{n - 6}} + 2{a^{n - 7}}\\ \;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - v} \right) + {a^{n - 4}} + 3{a^{n - 6}} \le {a^n}(2{a^{ - 4}} + \\ {a^{ - 5}} + 5{a^{ - 6}} + 4{a^{ - 7}})<{a^n} \end{array} $

图 2 s不与v₁、v₃相邻，且s与t有相同邻点 Fig.2 Case where s isn't adjacent to v₁, v₃ and s, t have same neighborhoods

否则, 1≤|N(t)∩N(s)|≤2, 即图G-v-s具有图 3所示的3种子结构之一。根据归纳假设及引理4, 有

$ \begin{array}{l} \;\;\;\;\;\;\;\phi \left( {G - v - s} \right) \le {\rm{max}}\{ {a^{n - 8}} + {a^{n - 5}} + 2{a^{n - 6}}, 2{a^{n - 8}} + \\ {a^{n - 4}} + {a^{n - 6}}, {a^{n - 7}} + {a^{n - 8}} + {a^{n - 4}} + {a^{n - 6}}\} = {a^{n - 7}} + {a^{n - 8}}\\ + {\rm{ }}{a^{n - 4}} + {a^{n - 6}} \end{array} $

图 3 s, t的共同邻点数为1或2 Fig.3 Case where s, t have one or two common neighborhoods

设$ {E_2} = \sum\limits_{u \in {N_{G - v(s)}}} {\phi \left( {G - v - N\left[ s \right] \cup N\left[ u \right]} \right)} $, 则有

$ \begin{array}{l} \;\;\;\;\;\;\;{E_2} \le {\rm{max}}\{ 3{a^{n - 6}}, 2{a^{n - 6}} + {a^{n - 7}}, {a^{n - 6}} + 2{a^{n - 7}}\} = \\ 3{a^{n - 6}}\\ \;\;\;\;\;\;\;\phi \left( {G - v} \right) \le \phi \left( {G - v - s} \right) + {a^{n - 5}} + {E_2}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi \left( {G - v} \right) + {a^{n - 4}} + 3{a^{n - 6}} \le {a^n}(2{a^{ - 4}} + \\ {a^{ - 5}} + 7{a^{ - 6}} + {a^{ - 7}} + {a^{ - 8}})<{a^n} \end{array} $

情况2 图G中包含C₃

设v、v₁、v₂是C₃的3个顶点, N(v₁)={v, v₂, t}且N(v₂)={v, v₁, s}。

子情况2.1 N(v₃)∩(N(v₁)∪N(v₂))={v}(图 4)。

图 4 v₁, v₂, v₃有共同邻点v Fig.4 Case where v₁, v₂, v₃ have a common neighborhood v

注意到在图G-v₃中有N[v]⊆N[v₁], 在图G- v₃-v₁中存在悬挂点v, 且d_G-v₃-v₁(s)=3。因此

$ \begin{array}{l} \;\;\;\;\;\;\;\phi (G - {v_3} - {v_1}) \le {a^{n - 7}} + {a^{n - 4}} + {a^{n - 5}}\\ \;\;\;\;\;\;\;\phi (G - {v_3}) \le \phi (G - {v_3} - {v_1}) + {a^{n - 5}} + {a^{n - 6}} + {a^{n - 7}}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi (G - {v_3}) + {a^{n - 4}} + 2{a^{n - 5}} + {a^{n - 6}} \le {a^n}\\ (2{a^{ - 4}} + 4{a^{ - 5}} + 2{a^{ - 6}} + 2{a^{ - 7}})<{a^n} \end{array} $

子情况2.2 图G具有以下两种子结构(图 5)：

图 5 s的邻点分布 Fig.5 Neighborhood distribution of s

(1) 当t≠v₃时, 有N(s)={t, v₂, v₃}；

(2) 当t=v₃时, 有N(s)={w, v₂, v₃}。

因图$ G - N\left[ s \right] \cong v{v_1} \cup (G - N\left[ s \right] - \{ v, {v_1}\} ), $则$\phi \left( G \right) \le {a^{n - 1}} + {a^{n - 6}} + 3{a^{n - 6}} = {a^n}({a^{ - 1}} + 4{a^{ - 6}})<{a^n} $

子情况2.3 N(v₃)={v, q, v₂}且t q, 如图 6所示。

图 6 v₁, v₃有两个公共邻点且非公共邻点不相邻 Fig.6 Case where v₁, v₃ have two common neighborhoods and the different neighborhoods are nonadjacent

注意到在图G-v₃中有N[v]⊆N[v₁], 且图$ G - {v_3} - {v_1} \cong v{v_2} \cup (G - \{ v, {v_1}, {v_2}, {v_3}\} ), $则由归纳假设可得

$ \begin{array}{l} \;\;\;\;\;\;\;\phi (G - {v_3}) \le {a^{n - 4}} + 2{a^{n - 5}} + {a^{n - 7}}\\ \;\;\;\;\;\;\;\phi \left( G \right) \le \phi (G - {v_3}) + {a^{n - 4}} + 2{a^{n - 5}} + {a^{n - 6}} \le {a^n}\\ (2{a^{ - 4}} + 4{a^{ - 5}} + {a^{ - 6}} + {a^{ - 7}})<{a^n} \end{array} $

子情况2.4 当v₃=t=s时有图$ G \cong {K_4}, $直接计算可知ϕ(G)=6=a⁴。

综上, 定理1得证。

3 结束语

本文采用不断细化图结构的方法，对给定顶点个数n且最大度至多为3的图上极大分离集进行研究，最终得到其极值结果，即该图类上极大分离集个数至多为$ {6^{\frac{\mathit{n}}{4}}}$，并刻画了相应的极图结构。

参考文献

[1]	MOON J W, MOSER L. On cliques in graphs[J]. Israel Journal of Mathematics, 1965, 3: 23-28. DOI:10.1007/BF02760024
[2]	FVREDI Z. The number of maximal independent sets in connected graphs[J]. Journal of Graph Theory, 1987, 11(4): 463-470. DOI:10.1002/jgt.3190110403
[3]	GRIGGS J R, GRINSTEAD C M, GUICHARD D R. The number of maximal independent sets in a connected graph[J]. Discrete Mathematics, 1988, 68: 211-220. DOI:10.1016/0012-365X(88)90114-8
[4]	HUJTER M, TUZA Z. The number of maximal independent sets in triangle-free graphs[J]. SIAM Journal on Discrete Mathematics, 1993, 6(2): 284-288. DOI:10.1137/0406022
[5]	LIU J Q. Maximal independent sets in bipartite graphs[J]. Journal of Graph Theory, 1993, 17(4): 495-507. DOI:10.1002/jgt.3190170407
[6]	KOH K M, GOH C Y, DONG F M. The maximum number of maximal independent sets in unicyclic connected graphs[J]. Discrete Mathematics, 2008, 308: 3761-3769. DOI:10.1016/j.disc.2007.07.079
[7]	SAGAN B E, VATTER V R. Maximal and maximum independent sets in graphs with at most r cycles[J]. Journal of Graph Theory, 2006, 53(4): 283-314. DOI:10.1002/jgt.20186
[8]	ALVARADO J D, DANTAS S, MOHR E, et al. On the maximum number of minimum dominating sets in forests[J]. Discrete Mathematics, 2018, 342: 934-942.
[9]	CONNOLLY S, GABOR Z, GODBOLE A, et al. Bounds on the maximum number of minimum dominating sets[J]. Discrete Mathematics, 2016, 339: 1537-1542. DOI:10.1016/j.disc.2015.12.030
[10]	FOMIN F V, GRANDONI F, PYATKIN A V, et al. Bounding the number of minimal dominating sets: a measure and conquer approach[M]//DENG X, DU D Z. Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Berlin: Springer, 2005: 573-582.
[11]	XIAO M Y, KOU S W. Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems[J]. Theoretical Computer Science, 2017, 657: 86-97. DOI:10.1016/j.tcs.2016.04.043
[12]	COUTURIER J, HEGGERNES P, VAN'T HOF P, et al. Maximum number of minimal feedback vertex sets in chordal graphs and cographs[M]//GUDMUNDSSON J, MESTRE J, VIGLAS T. Computing and Combinatorics. COCOON 2012. Lecture Notes in Computer Science, vol 7434. Berlin: Springer, 2012: 133-144.
[13]	FOMIN F V, GASPERS S, PYATKIN A V, et al. On the minimum feedback vertex set problem: exact and enumeration algorithms[J]. Algorithmica, 2008, 52(2): 293-307. DOI:10.1007/s00453-007-9152-0
[14]	YANNAKAKIS M. Node-deletion problems on bipartite graphs[J]. SIAM Journal on Computing, 1981, 10(2): 310-327. DOI:10.1137/0210022
[15]	KARDOŠ F, KATRENIČ J, SCHIERMEYER I. On computing the minimum 3-path vertex cover and dissociation number of graphs[J]. Theoretical Computer Science, 2011, 412(50): 7009-7017. DOI:10.1016/j.tcs.2011.09.009
[16]	ORLOVICH Y, DOLGUI A, FINKE G, et al. The complexity of dissociation set problems in graphs[J]. Discrete Applied Mathematics, 2011, 159(13): 1352-1366. DOI:10.1016/j.dam.2011.04.023
[17]	TU J H, ZHANG Z P, SHI Y T. The maximum number of maximum dissociation sets in trees[J]. Journal of Graph Theory, 2021, 96(4): 472-489. DOI:10.1002/jgt.22627
[18]	TU J H, LI Y X, DU J F. Maximal and maximum dissociation sets in general and triangle-free graphs[EB/OL]. (2021-03-02)[2021-07-24]. http://arxiv.org/abs/2103.01402v1.