含4—圈且不含3—圈的P4—等可覆蓋圖的刻畫

大學等一些重要的研究機構，有許多專家在從事這方面的研究。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的同一個結點合并而成的圖。