翟冬陽 曾德炎

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

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

中圖分類號：O157.5??文獻標識碼：A

一、介紹

本文所研究的圖都是簡單圖。在本文中，一個圖的階數(shù)是指這個圖的頂點的個數(shù)。我們用Pm、Km和Km，n表示m階路、m階完全圖以及m+n階完全二部圖。用Km表示m階完全圖的補圖。設(shè)H、G為兩個簡單圖，記E（H，G）={uv|u∈V（H），v∈V（G）}。H∪G表示頂點集為V（H）∪V（G），邊集為E（H）∪E（G）的圖。H∨G表示頂點集為V（H）∪V（G），邊集為E（H）∪E（G）∪E（H，G）的圖。設(shè)v∈V（G），XV（G），那么NX（v）表示在X中與v相鄰的點所構(gòu)成的點集。用G［X］表示在圖G中由點集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)，未定義的標記參考文獻［1］。

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

設(shè)G是一個頂點數(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)造三類圖如下：

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

iSymbolcB@

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

iSymbolcB@

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

iSymbolcB@

p。顯然圖G（3p+2）有3p+2個頂點。

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

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

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

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

設(shè)G是一個頂點數(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）三類圖如下：

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

iSymbolcB@

p。顯然圖G（k，pk+p）有pk+p個頂點。當n=pk+p+1時，構(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ǔ)上增加新的頂點x1，…，xp，并讓xi與v1，…，vik連邊構(gòu)造而成，這里1SymbolcB@

iSymbolcB@

p。顯然圖G（k，pk+p+1）有pk+p+1個頂點。當n=pk+p+q時，這里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ǔ)上增加新的點x1，…，xp，并讓xi與v1，…，vik連邊構(gòu)造而成，這里1SymbolcB@

iSymbolcB@

p。顯然G（k，pk+p+q）的頂點數(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是任意一個頂點數(shù)為n的k樹，其中n=pk+p，則圖G（k，pk+p）包含G作為子圖。

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

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

qSymbolcB@

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

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

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

當k=2，p=2時，H（k，pk+p+1）=H（2，7）=K2∨（K1∨2K2），如圖2所示。它是包含所有7個頂點的2樹作為子圖。

圖2?K2∨（K1∨2K2）

二、證明

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

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

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

（2）G中度為k的頂點都是G的耳朵；

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

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

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

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

引理1：設(shè)G是一個頂點數(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。顯然，當m=1時，G＼V′是Kk+2-m∪K1，m的子圖。

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

若sSymbolcB@

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

s-1。由sSymbolcB@

k+1，有mSymbolcB@

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

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

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

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

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

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

tSymbolcB@

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

定理7的證明：設(shè)G是一個頂點數(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中存在一個耳朵u，使得G＼（NG（u）∪{u}）是某個頂點數(shù)為2k+3的k樹的子圖。令M1=H（k，pk+p+1）＼{v1，v2，…，vk，x1}，則M1=K2k-2∨（K1∨2K2），從而M1包含所有2k+3個頂點的k樹作為子圖。因此M1包含G＼（NG（u）∪{u}）作為子圖。我們將G中的點集NG（u）與點u對應(yīng)放置到H中的點集{v1，v2，…，vk}與點x1上，有H（k，pk+p+1）包含G作為子圖。

若p>3，根據(jù)引理3，在G中存在一個耳朵u，使得G＼（NG（u）∪{u}）是某個頂點數(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的個頂點k樹的子圖，由于G＼（NG（u）∪{u}）是某個頂點數(shù)為（p-1）k+（p-1）+1的k樹的子圖，從而有M1包含G＼（NG（u）∪{u}）作為子圖。我們將G中的點集NG（u）與點u對應(yīng)放置到H中的點集{v1，v2，…，vk}與點x1上，有H（k，pk+p+1）包含G作為子圖。證畢。

參考文獻：

［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］.黑龍江科學，2021，14：3539.

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

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

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

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