给定度序列的双圈图的极值图

杨 杨，邵燕灵

(中北大学 理学院，山西 太原 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相关联的连接函数. 因此，在一定约束条件下的图的极值结构可以通过统一的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可以得到以下推论.