大学等一些重要的研究机构，有许多专家在从事这方面的研究。1985年，S.Ruiz引入了随机H-可分解图的概念，并刻划了H分别为p3和M2时的随机H-可分解图的特征。作为随机H-可分解性的放松，数学家B.L.Harthell和P.D.Vestergaard引入H-等可填充图的概念，并刻划了围长大于等于5的H-等可填充图的特征。接下来，B.Randerath和P.D.Vestergaard给出了所有H-等可填充图的特征。2008年，Zhang引出H-等可填充图的对偶的概念：H-等可覆盖图的概念，并完全刻划了H-等可覆盖图的特征。2009年，Zhang等给出了M2-等可覆盖图的一些结论，并刻画了几类特殊的M2-等可覆盖图，并已完全刻画了M2-等可覆盖图的特征。在本文中，我们给出所有含4-圈且不含3-圈的P4-等可覆盖图的刻画。
1.2 基本定义
令H为某一固定的图。如果图G的每一条边都至少出现在某一个子图Hi（i=1，2，…k中，即，则称为G的一个H-覆盖。设为图G的一个H-覆盖，若对于任意Hj（j∈{l，2，3，…k}），均不是G的一个覆盖，则称为G的一个极小H-覆盖。设H1，H2，…Hk为G的一个H-覆盖，如果不存在少于k个同构于H的子图可以覆盖图G，则称H，H2，…Hk为G的一个最小H-覆盖。如果G的每个极小H-覆盖都是G的最小H-覆盖，则称G为H-等可覆盖的。我们用MG（L）表示G的一个极小H-覆盖L=H1，H2，…Hk的覆盖数，用mG（L）表示G的最小H-覆盖的覆盖数。
命题 1.1 一个连通图G是P4-可覆盖的当且仅当它有一个子图P4。
显然，如果一个连通图G是P4-可覆盖的，它至少含有3条边。注意到当G同构于K1，t（t>3），那么它不是P4-可覆盖的。所以在下文中描述的阶数大于等于4的P4-可覆盖图中，不含有K1，t（t>3）。
命题 1.2 一个图G是P4-可覆盖的当且仅当它的每一个连通分支都是P4-可覆盖的。
引理 1.3G是一个连通图。如果G可以分解为几个连通的P4-可覆盖图，且它们中的至少一个不是P4-等可覆盖的，那么G不是P4-等可覆盖的。
引理 1.4G是一个树。我们将G中不相邻的两点合并为一点从而得到了一个含圈的新图G’。如果G不是P4-等可覆盖的，那么G’不是P4-等可覆盖的。
2 主要结论
首先，我们刻画了p4-等可覆盖的路和圈。
引理 2.1 路Pn是P4-等可覆盖的当且仅当n=4，5，6，7，8，11.
引理 2.2 圈Cn是P4-等可覆盖的当且仅当n=4，5，7.
下面，我们给出一个有用的结论。
定义 2.3 对于星Ki，t，我们将其中度为k的结点称为中心结点，其他结点称为端点（树叶）。在星K1，t的每条边上都插入一个2度结点所得的树称为一个k-扩星。即k-扩星有一个度k结点（称为扩星的中心），k个度2结点，k片树叶。我们记之为在k-扩星的每条边上都插入一个2度结点所得的树称为一个二阶k-扩星，记之为类似地，n阶k-扩星是通过在n-l阶k-扩星的每条边上都插入一个2度结点所得到的。
下面的引理很容易验证是正确的：
引理 2.4 每一个二阶k扩星都是P4-等可覆盖的。
注释 2.5 显然，P4可以表示为而P7可以表示为.
引理 2.6 G是一个连通图且非圈。如果G不含3-圈且含有4-圈，那么G不是P4-等可覆盖的，除非G是（n>l）或者G是由n个P2·K1，t（t>3）中p2部分的度1结点与C4中的同一个结点合并而构成的图。
证明：情形1：G是由若干个p2和C4合并而成的图。
（1）如果C4的每一个结点只能与至多一个P2的端点合并，那么G只可能是图1中的五种情况之一。对于图1中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG（L）大于最小覆盖的覆盖数m （G）。所以图1中的图都不是P4-等可覆盖的。
（2）如果C4的每一个结点可以与多个p2的端点合并，那么G可以看作是由多个P2的端点与G’中的4-圈部分的结点合并而成，其中G’为图1中的图之一。如果p2的数目为n，我们可以找到一个覆盖数为M（G’）+n的极小P4覆盖（用M（G’）个P4覆盖G’部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m（G’）+n。对于每一个G’，都存在一个它的极小覆盖，其覆盖数M（G’）>m（G’），因此G不是P4-等可覆盖的。
情形 2：G是由若干个P3和C4合并而成的图。
注意到我们是将每一个P3的端点而不是中心点与C4的结点合并，否则的话G就与情形1中的某些图重复了。
（1）如果C4的每一个结点只能与至多一个P3的端点合并，那么G只可能是图2中的五种情况之一，对于图2中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG（L）大于最小覆盖的覆盖数m（G）。所以图2中的图都不是P4-等可覆盖的。
（2）如果C4的每一个结点可以与多个P2的端点合并，那么G可以看作是由多个P2的端点与G’中的4-圈部分的结点合并而成，其中G’为图2中的图之一。如果P2的数目为n，我们可以找到一个覆盖数为M（G’）+n的极小P4覆盖（用M（G’）个P4覆盖G’部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m（G’）+n。对于每一个G’，都存在一个它的极小覆盖，其覆盖数M（G’）>m（G’），因此G不是P4-等可覆盖的。
情形 3：G是由若干个P2和若干个P3与C4合并而成的图。
如果只有若干个P2或者若干个P3，那么与情形1或情形2相同。否则，
（1）如果C4的每一个结点只能与至多一个P2或P2的端点合并，那么G只可能是图3中的九种情况之一。对于图3中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG（L）大于最小覆盖的覆盖数m（G）。所以图3中的图都不是P4-等可覆盖的。
（2）如果C4的每一个结点可以与多个P2或P2的端点合并，那么G可以看作是由多个P2或P3的端点与G’中的4-圈部分的结点合并而成，其中G’为图2中的图之一。如果p2和P3的总数目为n，我们可以找到一个覆盖数为M（G’）+n的极小P4覆盖（用M（G’）个P4覆盖G’部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m（G’）+n。对于每一个G’，都存在一个它的极小覆盖，其覆盖数M（G’）>m（G’），因此G不是P4-等可覆盖的。
（3）容易验证，图4中的图不是P4-等可覆盖的。如果C4中的一个或多个结点与至少一个P，和一个P2的端点合并，那么G可分解为两部分： P4和一个非P4-等可覆盖的图。
情形4：G是由若干个星K1，t（t>3）和C4合并而成的图。
注意到我们是将每一个星K1，t（t>3）的端点而不是中心点与C4的结点合并，否则的话G就与情形1中的某些图重复了。
当t=3时，
（1）如果C4的每一个结点只能与至多一个星K1，（t>3）的端点合并，那么只可能得到5个可能的图。容易验证这5个图都不是P4-等可覆盖的。
（2）如果C4的每一个结点可以与多个P2或P3的端点合并，那么G可以分解为n个K1，t和一个图G’，其中图G’是（1）中一个非P4-等可覆盖的图。记G’的一个极小P4覆盖的覆盖数为M（G’），那么图G存在一个覆盖数为M（G’）+n的极小P4覆盖，而图G的最小P4覆盖的覆盖数不会大于m（G’）+n.于是G不是P4-等可覆盖的。
当t >4时，我们可以找到G’的一个极小P4覆盖，其覆盖数为M（G-）+（t一3）>m（G-）+（t-3）（用M（G’）个P4覆盖G-部分，用（t-3）个P4覆盖其余部分）。而图G的最小P4覆盖的覆盖数不会大于m（G’）+n.于是G不是P4-等可覆盖的。
情形 5：G是由若干个p2和若干个K1，t（t>3）与C4合并而成的图。
注意到我们是将每一个星K1，t（t>3）的端点而不是中心点与C4的结点合并。如果只有若干个p2或者若干个K1，t（t>3），那么与情形1或情形4相同。否则，
当t=3时，
（1）如果C4的每一个结点只能与至多一个P，或K1，3的端点合并，那么G只可能是图5中的九种情况之一。对于图5中的每一个图，我们都可以找到一个极小覆盖L，使得它的覆盖数MG （L）大于最小覆盖的覆盖数m（G）。所以图5中的图都不是P4-等可覆盖的。
（2）如果C。的每一个结点可以与多个P，或K1，t的端点合并，那么G可以看作是由多个P2或K1，3的端点与G’中的4-圈部分的结点合并而成，其中G’为图5中的图之一。如果P，和K1，3的总数目为n，我们可以找到一个覆盖数为M（G’）+n的极小P4覆盖（用M（G’）个P4覆盖G’部分，用n个P4覆盖其余部分），而最小覆盖的覆盖数不会多于m （G’）+n。对于每一个G’，都存在一个它的极小覆盖，其覆盖数M（G’）>m（G’），因此G不是P4-等可覆盖的。
（3）我们将图6中的图记为G’。由于存在一个极小覆盖，其覆盖数M（G’）=4>3=m（G’），所以G’不是P4-等可覆盖的。如果C4的一个或多个结点与至少一个P2和K1，3合并，那么G可以被分解为两部分：P2和一个非P4-等可覆盖图。
当t >4时，我们可以找到G’的一个极小P4覆盖，其覆盖数为M（G’）+（t-3）>m （G’）+（t-3）（用M（G’）个P4覆盖G’部分，用（t-3）个P4覆盖其余部分）。而图G的最小P4覆盖的覆盖数不会大于m（G’）+n.于是G不是P4-等可覆盖的。
情形 6：G是由若干个P2和若干个K1，t（t>3）与C4合并而成的图。
注意到我们是将每一个星K1，t（t>3）的端点而不是中心点与C4的结点合并。如果只有若干个P3或者若干个K1，t（t>3），那么与情形2或情形4相同。否则，
与情形5类似，G不是P4-等可覆盖的。
情形 7：G是由若干个P2，P3和若干个K1，t（t>3）与C4合并而成的图。
注意到我们是将每一个星Kl，t（t>3）的端点而不是中心点与C4的结点合并。我们只需要考虑若干个P2，P3和若干个K1，t（t>3）同时与C4合并的情形。否则，G与之前情形中的某些图相同。
与情形5类似，G不是P4-等可覆盖的。
情形8：G是由若干个P4和C4合并而成的图。
注意到我们是将每一个P4的端点与C4的结点合并，否则的话G就与之前情形中的某些图重复了。
（1）如果n个P4的端点只能与C4的一个结点合并，那么极小覆盖数MG（L）和最小P4覆盖数m（G）都是n+2。我们将这个图记作，它是P4-等可覆盖的。
（2）如果n个P4的端点可以与C4的至少两个结点合并，那么存在一个覆盖数MG（L）=n+3的极小P4覆盖，而最小P4覆盖数m（G）是n+2，因为MG（L）>m（G），所以G不是P4一等可覆盖的。
情形9：G是由若干P2K1，t（t>3）和C4合并而成的图。
我们将P2的一个端点与K1，t（t>3）的一个端点合并得到的图记作P2·K1，t（t>3）。我们将P2.K1，t（t>3）中的P2部分的端点与C4的结点合并，否则G就与之前情形中的某些图重复了。
（1）如果n个P2·K1，t（t>3）只能与C4的一个结点合并，那么极小覆盖数MG （L）和最小P4覆盖数m（G）都是n（t-l）+2。它是P4-等可覆盖的。
（2）如果n个P2·Kl·t（t>3）可以与C4的至少两个结点合并，那么存在一个覆盖数MG（L）=n（t-1）+3的极小P4覆盖，而最小P4覆盖数m（G）是n（t-1）+2，因为MG（L）>m（G），所以G不是P4-等可覆盖的。
情形10：G不属于情形1-9。
每一个图G可以被分解为2个连通的部分：一个包含于情形1-9中的非P4-等可覆盖图和一个P4-可覆盖图。由引理1.4，G不是P4-等可覆盖的。
综上，G不是P4-等可覆盖的，除非G是C4·Sn2*（n>l）或者是由n个P2·Kl，t（t>3）与C4的同一个结点合并而成的图。
相关热词搜索： 不含 刻画 覆盖 P4
