給定度序列的雙圈圖的極值圖

楊 楊，邵燕靈

(中北大學 理學院，山西 太原 030051)

0 引 言

本文研究的所有圖均為簡單連通圖. 設G=(V,E)是頂點集為V(G)={v1,v2,…,vn}，邊集合為E(G)的圖. 設v∈V(G)，用N(v)表示點v的鄰點集合，d(v)表示點v的度，稱(d(v1),d(v2),…,d(vn))為圖G的度序列. 給定一個非負整數序列π，如果存在一個簡單連通圖G使得G的度序列為π，則稱π為可圖度序列. 本文給定的度序列均為非遞增序列π=(d0,d1,…,dn-1). 一個含有n個頂點n條邊的簡單連通圖稱為單圈圖； 含有n個頂點n+1條邊的簡單連通圖稱為雙圈圖[1-2]. 用gπ表示所有度序列為π的簡單連通圖的集合，Uπ表示所有度序列為π的單圈圖的集合，Bπ表示所有度序列為π的雙圈圖的集合.

(1)

式中：f(x,y)為定義在N×N上的一個二元函數，Rf為與f相關聯的連接函數. 因此，在一定約束條件下的圖的極值結構可以通過統(tǒng)一的Rf來表現.

定義1[10-11]設f(x,y)為N×N上的二元函數，如果對任意x≥y和a≥b，有f(y,a)+f(x,b)≤f(x,a)+f(y,b), 當且僅當x=y,a=b時等號成立，則稱f(x,y)是遞增函數. 相似地，如果對任意x≥y和a≥b，f(y,a)+f(x,b)≥f(x,a)+f(y,b)，當且僅當x=y,a=b時等號成立，則稱f(x,y)為遞減函數.

文獻[11]利用連接函數Rf研究了不同度序列的極值樹. 文獻[12]研究了gπ的最大化與遞增函數f相關聯的Rf的極值樹性質，及極值單圈圖Uπ的最大化或最小化的Rf. 本文將在此基礎上，研究在給定度序列的情況下，雙圈圖Bπ最大化或最小化的Rf的極值圖，并給出一個算法構造其極值圖.

1 相關引理

定義2[11]給定一個圖的度序列，運用以下貪婪算法得到的樹稱為貪婪樹：

1) 將給定的度序列中的最大度頂點標記為v，作為根部；

2) 標注v的鄰點為v1,v2,…，指定其中的最大可用度，使得d(v1)≥d(v2)≥…；

3) 標記v1的鄰點(除去v)為v11,v12,…, 得到他們的最大可用度，使得d(v11)≥d(v12)≥…，對v2,v3,…的鄰點用同樣的方法進行標記；

4) 對新標記的頂點重復3)，并且總是從度較大的已標記頂點的尚未標記的鄰點開始.

引理1[10-11]對任意遞增函數f，Rf在給定度序列中被貪婪樹最大化.

引理2[10-11]對任意遞減函數f，Rf在給定度序列中被貪婪樹最小化.

定義3設uv為圖G的任意一條邊，G-uv表示從G中刪除邊uv得到的圖. 類似地，設u,v∈V(G)，uv?E(G)，G+uv表示在G中添加一條邊uv所得到的圖.

引理3[12]設f是一個遞增函數，G∈gπ，uv，xy∈E(G)且uy，xv?E(G). 設H=G-uv-xy+uy+xv，如果d(u)≥d(x)且d(y)≥d(v)，則Rf(G)≤Rf(H).

引理4[12]對于遞增函數f，存在一個極值圖G在gπ上使Rf最大化，并把G中的頂點標記為{v1,v2,…,vn}，v1為圖G的根點，可滿足以下條件：

1) 0≤h(v1)≤h(v2)≤…≤h(vn)，其中h(v)表示頂點v到根點v1的距離；

2)d(v1)≥d(v2)≥…≥d(vn)；

3) 假設vivj，vsvt∈E(G)，vivt，vsvt?E(G)，h(vj)=h(vt)=h(vi)+1=h(vs)+1，如果i

引理5[10]一個定義在N×N上的二元函數f(x,y)=(x+y)α，α≥1時，f(x,y)是遞增函數； 0<α<1時，f(x,y)是遞減函數.

引理6[10]一個定義在N×N上的二元函數f(x,y)=xαyα，α>0時，f(x,y)是遞增函數；α<0時，f(x,y)是遞減函數.

2 主要結論

定理1設n≥5,π=(d0,d1,d2,…,dn-1)是一個可圖雙圈圖的度序列，d0≥d1≥3,dn-1=1，則對任意遞增函數f，存在一個極值圖G在Bπ上使Rf最大化，使得v1v2,v1v3,v1v4,v2v3,v2v4∈E(G)，且對所有x∈V(G){v1,v2,v3,v4}，有d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(x).

證明根據引理4，存在一個極值圖G在Bπ上使Rf最大化，并把G中的頂點標記為{v1,v2,…,vn}，v1為圖G的根點，可滿足以下條件：

1) 0≤h(v1)≤h(v2)≤…≤h(vn)，其中h(v)表示頂點v到根點v1的距離；

2)d(v1)≥d(v2)≥…≥d(vn)；

3) 假設vivj，vsvt∈E(G)，vivt，vsvt?E(G)，h(vj)=h(vt)=h(vi)+1=h(vs)+1，如果i

1) 若vt-1,kvti,vt-1,kvtj∈E(G)且i

2) 若vt-1,kvti,vt-1,lvtj∈E(G)且k

我們將證明以下4個斷言成立.

由以上4個斷言可知，對任意遞增函數f，必存在一個極值圖G，在Bπ上使Rf最大化，若記v1=v01,v2=v11,v3=v12,v4=v13，則v1v2,v1v3,v1v4,v2v3,v2v4∈E(G)，且對所有的x∈V(G){v1,v2,v3,v4}，有d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(x). 定理證畢.

圖

通過引理5～7和定理2可以得到以下推論.