包含所有固定階數(shù) k 樹的一類圖

翟冬陽 曾德炎

摘?要：圖G是k樹當(dāng)且僅當(dāng)G是一個(gè)頂點(diǎn)數(shù)為k+1的完全圖，或者在圖G中能找到度為k的點(diǎn)v，使得與v相鄰的k個(gè)點(diǎn)構(gòu)成的點(diǎn)集為團(tuán)，且G＼v也是一個(gè)k樹。設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的k樹，其中n=pk+p+1，p2。本文構(gòu)造了一類新的圖包含G作為子圖。

關(guān)鍵詞：k樹；完全圖；子圖

中圖分類號：O157.5??文獻(xiàn)標(biāo)識碼：A

一、介紹

本文所研究的圖都是簡單圖。在本文中，一個(gè)圖的階數(shù)是指這個(gè)圖的頂點(diǎn)的個(gè)數(shù)。我們用Pm、Km和Km，n表示m階路、m階完全圖以及m+n階完全二部圖。用Km表示m階完全圖的補(bǔ)圖。設(shè)H、G為兩個(gè)簡單圖，記E（H，G）={uv|u∈V（H），v∈V（G）}。H∪G表示頂點(diǎn)集為V（H）∪V（G），邊集為E（H）∪E（G）的圖。H∨G表示頂點(diǎn)集為V（H）∪V（G），邊集為E（H）∪E（G）∪E（H，G）的圖。設(shè)v∈V（G），XV（G），那么NX（v）表示在X中與v相鄰的點(diǎn)所構(gòu)成的點(diǎn)集。用G［X］表示在圖G中由點(diǎn)集X所誘導(dǎo)的子圖。記G＼v=G［V（G）＼v］，G＼X=G［V（G）＼X］。用Km-E（H）表示在Km的基礎(chǔ)上刪除掉圖H對應(yīng)的邊所得到的圖。在本文出現(xiàn)，未定義的標(biāo)記參考文獻(xiàn)［1］。

圖G是k樹當(dāng)且僅當(dāng)G是一個(gè)頂點(diǎn)數(shù)為k+1的完全圖，或者在G中能夠找到度為k的點(diǎn)v，使得與v相鄰的k個(gè)點(diǎn)構(gòu)成的點(diǎn)集為團(tuán)，且G/v也是一個(gè)k樹。1樹就是我們通常所說的樹。在k樹中我們把度為k的頂點(diǎn)稱為這個(gè)k樹的耳朵。顯然，對于任意一個(gè)頂點(diǎn)為n的k樹G，若n≠k+1，則都能在某個(gè)頂點(diǎn)數(shù)為n-1的k樹G'的基礎(chǔ)上增加一個(gè)度為k的新頂點(diǎn)u，讓u與G'中某k個(gè)階團(tuán)中的頂點(diǎn)v1，v2，…，vk均連邊構(gòu)造而成。我們稱這個(gè)過程為將耳朵u粘貼到團(tuán){v1，v2，…，vk}上。設(shè)T（k，n）=Kk∨Kn-k。顯然，T（k，n）是一個(gè)頂點(diǎn)數(shù)為n，耳朵數(shù)為n-k的k樹，并且是同一個(gè)團(tuán)被這n-k個(gè)耳朵粘貼。

設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的2樹，其中n3，設(shè)n≡q（mod3），其中q=0，1，2。我們設(shè)n=3p+q，其中q=0，1，2。對于q=0，1，2，分別構(gòu)造三類圖如下：

當(dāng)n=3p時(shí)，G（3p）構(gòu)造如下：設(shè)V（K2p）={v1，…，v2p}，G（3p）是在圖K2p的基礎(chǔ)上增加新的點(diǎn)x1，…，xp，并讓xi與v1，…，v2i連邊構(gòu)造而成，其中1SymbolcB@

iSymbolcB@

p。顯然圖G（3p）有3p個(gè)頂點(diǎn)。當(dāng)k=3p+1，p3時(shí)，G（3p+1）構(gòu)造如下：設(shè)V（K2p+1）={v1，…，v2p+1}，G（3p+1）是在圖K2p+1-v2p-2v2p的基礎(chǔ)上增加新的點(diǎn)x1，…，xp，并讓xi與v1，…，v2i連邊構(gòu)造而成，其中1SymbolcB@

iSymbolcB@

p。顯然圖G（3p+1）有3p+1個(gè)頂點(diǎn)。當(dāng)k=3p+2，p2時(shí)，G（3p+2）的構(gòu)造如下：設(shè)V（K2p+2）={v1，…，v2p+2}，G（3p+2）是在圖K2p+2-v2pv2p+2的基礎(chǔ)上增加新的點(diǎn)x1，…，xp，并讓xi與v1，…，v2i連邊構(gòu)造而成，這里1SymbolcB@

iSymbolcB@

p。顯然圖G（3p+2）有3p+2個(gè)頂點(diǎn)。

曾德炎［45］證明了這三類圖分別包含對應(yīng)頂點(diǎn)數(shù)的所有2樹作為子圖，得到了下面三個(gè)定理：

定理1：設(shè)G是任意一個(gè)頂點(diǎn)數(shù)為n的2樹，其中n=3p，p1，則G（3p）包含G作為子圖。

定理2：設(shè)G是任意一個(gè)頂點(diǎn)數(shù)為n的2樹，其中n=3p+1，p3，則G（3p+1）包含G作為子圖。

定理3：設(shè)G是任意一個(gè)頂點(diǎn)數(shù)為n的2樹，其中n=3p+2，p2，則G（3p+2）包含G作為子圖。

設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的k樹，其中nk+1。設(shè)n≡q（modk+1），其中q=0，1，…，k。為了方便，我們設(shè)k=pk+p+q，其中q=0，1，…，k。對于q=0，q=1和2SymbolcB@

qSymbolcB@

k這三種情形，我們分別構(gòu)造G（k，pk+p），G（k，pk+p+1）和G（k，pk+p+q）三類圖如下：

當(dāng)n=pk+p時(shí)，構(gòu)造G（k，pk+p）如下：設(shè)V（Kpk）={v1，v2，…，vpk}，G（k，pk+p）是在Kpk的基礎(chǔ)上增加新的點(diǎn)x1，…，xp，并讓xi與v1，…，vik連邊構(gòu)造而成，這里1SymbolcB@

iSymbolcB@

p。顯然圖G（k，pk+p）有pk+p個(gè)頂點(diǎn)。當(dāng)n=pk+p+1時(shí)，構(gòu)造G（k，pk+p+1）如下：設(shè)V（Kpk+1）={v1，…，vpk+1}，G（k，pk+p+1）是在Kpk+1-v（p-1）kvpk的基礎(chǔ)上增加新的頂點(diǎn)x1，…，xp，并讓xi與v1，…，vik連邊構(gòu)造而成，這里1SymbolcB@

iSymbolcB@

p。顯然圖G（k，pk+p+1）有pk+p+1個(gè)頂點(diǎn)。當(dāng)n=pk+p+q時(shí)，這里1SymbolcB@

qSymbolcB@

k，構(gòu)造G（k，pk+p+q）如下：設(shè)V（Kpk+q）={v1，…，vpk+q}，G（k，pk+p+q）是在Kpk+q-vpkvpk+q的基礎(chǔ)上增加新的點(diǎn)x1，…，xp，并讓xi與v1，…，vik連邊構(gòu)造而成，這里1SymbolcB@

iSymbolcB@

p。顯然G（k，pk+p+q）的頂點(diǎn)數(shù)為pk+p+q。圖1為G（2，7）。

圖1?G（2，7）

最近我們將定理13中關(guān)于2樹的結(jié)論推廣到了k樹，得到了相應(yīng)的定理46［6］：

定理4：設(shè)G是任意一個(gè)頂點(diǎn)數(shù)為n的k樹，其中n=pk+p，則圖G（k，pk+p）包含G作為子圖。

定理5：設(shè)G是任意一個(gè)頂點(diǎn)數(shù)為n的k樹，其中n=pk+p+1，p3。則圖G（k，pk+p+1）包含G作為子圖。

定理6：設(shè)G是任意一個(gè)頂點(diǎn)數(shù)為n的k樹，其中n=pk+p+q，p2，2SymbolcB@

qSymbolcB@

k。則圖G（k，pk+p+q）包含G作為子圖。

當(dāng)頂點(diǎn)數(shù)n=pk+p+1時(shí)，我們構(gòu)造了一個(gè)新的圖Kpk-2∨（K1∨2K2）∪Kp-2，顯然該圖的頂點(diǎn)數(shù)為pk+p+1。記H（k，pk+p+1）=Kpk-2∨（K1∨2K2）∪Kp-2。以下的定理7是本文的主要結(jié)論：

定理7：設(shè)G是一個(gè)頂點(diǎn)數(shù)為pk+p+1的k樹，其中p2。則H（k，pk+p+1）包含G作為子圖。

當(dāng)k=2，p=2時(shí)，H（k，pk+p+1）=H（2，7）=K2∨（K1∨2K2），如圖2所示。它是包含所有7個(gè)頂點(diǎn)的2樹作為子圖。

圖2?K2∨（K1∨2K2）

二、證明

為了證明定理7，我們用到下面這個(gè)已知的結(jié)論：

定理8［23］：設(shè)G是一個(gè)n階的k樹。則：

（1）G中的耳朵數(shù)大于等于2；

（2）G中度為k的頂點(diǎn)都是G的耳朵；

（3）若G不是頂點(diǎn)數(shù)為k+1的完全圖，那么在G中的任意兩個(gè)耳朵均不相鄰；

（4）G中不包含長度大于等于4的無弦圈；

（5）G中不包含頂點(diǎn)數(shù)為k+2的完全圖。

為證明定理7，我們還需要下面的一些引理：

引理1：設(shè)G是一個(gè)頂點(diǎn)數(shù)為2k+3的k樹，則存在V′V（G），其中|V′|=k存在整數(shù)m滿足1SymbolcB@

mSymbolcB@

k，使得G＼V′是Kk+2-m∪K1，m的子圖。

證明：設(shè)X={u1，u2，…，us}是G中所有耳朵構(gòu)成的集合。顯然，sSymbolcB@

k+3。設(shè)H=G＼X。

若s=k+3，則G=T（k，2k+3），且H=Kk。令V′=V（H），則G＼V′=Kk+3。顯然，當(dāng)m=1時(shí)，G＼V′是Kk+2-m∪K1，m的子圖。

若s=k+2，則H=Kk+1，且在H中有k+1個(gè)不同的Kk。由于X中有k+2個(gè)頂點(diǎn)，并且每個(gè)頂點(diǎn)與H中的一個(gè)Kk相鄰，則至少存在兩個(gè)不同的頂點(diǎn)ui，uj∈X，使得NH（ui）=NH（uj）。令V′=NH（ui）=NH（uj），顯然G＼V′是K1，k∪K1，1的子圖。從而，當(dāng)m=1時(shí)，G＼V′是Kk+2-m∪K1，m的子圖。

若sSymbolcB@

k+1，則H是某個(gè)頂點(diǎn)數(shù)為2k+3-sk+2的k樹。設(shè)v是H的一個(gè)耳朵，其中|NX（v）|=m。由于v不是G的一個(gè)耳朵，所以在X中至少有一個(gè)頂點(diǎn)與v相鄰，即m1。若m=s，由于H中至少有兩個(gè)耳朵，設(shè)u是H的另一個(gè)耳朵。因?yàn)閡也不是G的耳朵，所以|NX（u）|1。不妨設(shè)w∈NX（u），由m=s，有w∈NX（v），從而uw、vw∈E（G）。因?yàn)閣是G的耳朵，有uv∈E（G），從而uv∈E（H）。這與定理8（3）頂點(diǎn)數(shù)大于等于k+2的k樹中的任意兩個(gè)耳朵互不相鄰矛盾。因此，mSymbolcB@

s-1。由sSymbolcB@

k+1，有mSymbolcB@

k。令V′=NH（v），由于在G中由頂點(diǎn)集NX（v）∪{v}誘導(dǎo)的子圖為K1，m，有G＼V′是Kk+2-m∪K1，m的子圖。引理得證。

引理2：設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的k樹，其中nk+2。若v∈V（G），那么G＼v是某個(gè)頂點(diǎn)數(shù)為n-1的k樹的子圖。

證明：我們對n用歸納法。當(dāng)n=k+2時(shí)，由于Kk+1是唯一一個(gè)頂點(diǎn)數(shù)為k+1的k樹，且G-v的頂點(diǎn)數(shù)為k+1，從而G-v是Kk+1的子圖，也就是說G-v是某個(gè)頂點(diǎn)數(shù)為n-1的k樹的子圖。因此引理1對于n=k+2的情形是成立的。假設(shè)nk+3，設(shè)v是G的一個(gè)耳朵，則G-v是一個(gè)頂點(diǎn)數(shù)為n-1的k樹，也就是說引理2對于這種情形成立。因此假設(shè)v不是G的耳朵，設(shè)u是G的一個(gè)耳朵。若v與u相鄰，記G1=G-u，則G1是一個(gè)頂點(diǎn)數(shù)為n-1的k樹。因?yàn)镹G（u）NG（v），所以G＼v是G＼u的一個(gè)子圖，從而G＼v是某個(gè)頂點(diǎn)數(shù)為n-1的k樹G1的子圖。若v與u不相鄰，由G＼u是n-1階k樹，根據(jù)歸納假設(shè)可知，G＼{u，v}是某個(gè)頂點(diǎn)數(shù)為n-2的k樹G2的子圖。顯然NG（u）V（G2）且在G中由頂點(diǎn)集NG（u）誘導(dǎo)的子圖是頂點(diǎn)數(shù)為k的完全圖。我們在G2的基礎(chǔ)上構(gòu)造一個(gè)新圖G3。G3是在k樹G2的基礎(chǔ)上增加一個(gè)新的頂點(diǎn)u1，并讓u1與NG（u）中的任意一個(gè)頂點(diǎn)都相鄰。顯然G3就是在頂點(diǎn)數(shù)為n-2的k樹G2的基礎(chǔ)上增加了一個(gè)新的耳朵u1。也就是說G3是一個(gè)頂點(diǎn)數(shù)為n-1的k樹，同時(shí)G＼v是G3的子圖。引理得證。

引理3：設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的k樹，這里nk+2。設(shè)V'V（G），其中V'中頂點(diǎn)的個(gè)數(shù)為t，這里tSymbolcB@

n-k-1。則G＼V'某個(gè)頂點(diǎn)數(shù)為n-t的k樹的子圖。

證明：我們對t用歸納法。由引理2可以得到，引理3對于t=1的情形成立。我們現(xiàn)假設(shè)2SymbolcB@

tSymbolcB@

n-（k+1）。設(shè)v是V'中的一個(gè)點(diǎn)，根據(jù)歸納假設(shè)可知G＼（V'-v）是某個(gè)頂點(diǎn)數(shù)為n-（t-1）的k樹G1的子圖。根據(jù)引理2可知G1＼v是某個(gè)頂點(diǎn)數(shù)為n-t的k樹G2的子圖。由G-V'是G1-v的一個(gè)子圖，從而有G-V'也是某個(gè)頂點(diǎn)數(shù)為n-t的k樹G2的生成子圖。引理得證。

定理7的證明：設(shè)G是一個(gè)頂點(diǎn)數(shù)為pk+p+1的k樹，其中p2。我們對p用歸納法。為了方便描述，在H（k，pk+p+1）=Kpk-2∨（K1∨2K2）∪Kp-2中我們記V（Kpk-2）={v1，v2，…，vpk-2}，V（Kp-2）={x1，x2，…，xp-2}。

若p=2，則H=K2k-2∨（K1∨2K2）。根據(jù)引理1，存在V′V（G），其中|V′|=k，存在整數(shù)m滿足1SymbolcB@

mSymbolcB@

k，使得G＼V′是Kk+2-m∪K1，m的子圖。令M=H（k，pk+p+1）＼{v1，v2，…，vk}，則M=Kk-2∨（K1∨2K2）。顯然，對于滿足1SymbolcB@

mSymbolcB@

k的任意整數(shù)m，均有M包含Kk+2-m∪K1，m作為子圖。因此，M包含G＼V′作為子圖。我們將G中的V′放置到H中的{v1，v2，…，vk}上，由dH（v1）=dH（v2）=…=dH（vk）=2k+2，有H（k，pk+p+1）包含G作為子圖。

若p=3，根據(jù)引理3，在G中存在一個(gè)耳朵u，使得G＼（NG（u）∪{u}）是某個(gè)頂點(diǎn)數(shù)為2k+3的k樹的子圖。令M1=H（k，pk+p+1）＼{v1，v2，…，vk，x1}，則M1=K2k-2∨（K1∨2K2），從而M1包含所有2k+3個(gè)頂點(diǎn)的k樹作為子圖。因此M1包含G＼（NG（u）∪{u}）作為子圖。我們將G中的點(diǎn)集NG（u）與點(diǎn)u對應(yīng)放置到H中的點(diǎn)集{v1，v2，…，vk}與點(diǎn)x1上，有H（k，pk+p+1）包含G作為子圖。

若p>3，根據(jù)引理3，在G中存在一個(gè)耳朵u，使得G＼（NG（u）∪{u}）是某個(gè)頂點(diǎn)數(shù)為（p-1）k+（p-1）+1的k樹的子圖。令M1=H（k，pk+p+1）＼{v1，v2，…，vk，x1}，則M1=K（p-1）k-2∨（K1∨2K2）∪K（p-1）-2。根據(jù)歸納假設(shè)M1包含所有（p-1）k+（p-1）+1的個(gè)頂點(diǎn)k樹的子圖，由于G＼（NG（u）∪{u}）是某個(gè)頂點(diǎn)數(shù)為（p-1）k+（p-1）+1的k樹的子圖，從而有M1包含G＼（NG（u）∪{u}）作為子圖。我們將G中的點(diǎn)集NG（u）與點(diǎn)u對應(yīng)放置到H中的點(diǎn)集{v1，v2，…，vk}與點(diǎn)x1上，有H（k，pk+p+1）包含G作為子圖。證畢。

參考文獻(xiàn)：

［1］J.A.Bondy，U.S.R.Murty.Graph?Theory?With?Applications［M］.London：The?Macmillan?Press，1976.

［2］Bose，P.，Dujmovic，V.，Krizanc，D.，et?al.A?characterization?of?the?degree?sequences?of?2trees.J.GraphTheory，2008，58：191209.

［3］D.Y.Zeng，J.H.Yin.On?a?characterization?of?ktrees［J］.Czech.Math.J.，2015，65（140）：361365.

［4］曾德炎，翟冬陽.關(guān)于2樹子圖的一些性質(zhì)［J］.黑龍江科學(xué)，2021，14：3539.

［5］曾德炎，翟冬陽.包含所有固定階數(shù)2樹作為子圖的圖的構(gòu)造［J］.科技風(fēng)，2021，28：1012.

［6］翟冬陽，曾德炎.包含所有固定階數(shù)k樹作為子圖的圖的構(gòu)造［J］.科研管理，2022，5：250253.

基金項(xiàng)目：海南省自然科學(xué)基金項(xiàng)目“關(guān)于可圖序列的一類極值問題的研究”（No.122QN335）；青年教師專項(xiàng)培養(yǎng)科研項(xiàng)目“關(guān)于兩類特殊圖蘊(yùn)含函數(shù)的研究”（No.USYQNZX2154）

作者簡介：翟冬陽（1989—?），女，漢族，遼寧遼陽人，碩士，講師，研究方向：圖論及其應(yīng)用的研究；曾德炎（1989—?），男，漢族，湖北荊州人，碩士，副教授，研究方向：圖論及其應(yīng)用。