Advances in Applied Mathematics
Vol.07 No.04(2018), Article ID:24707,6 pages
10.12677/AAM.2018.74053

Judicious Balanced Bipartitions of (k, k − 1)-Biregular Graphic Degree Sequence

Haiyan Li, Jin Guo

College of Information Science and Technology, Hainan University, Haikou Hainan

Received: Apr. 11th, 2018; accepted: Apr. 21st, 2018; published: Apr. 28th, 2018

ABSTRACT

Let π = ( d 1 , d 2 , , d n ) be a graphic sequence of nonnegative integers and π 1 , π 2 are two sequences that are obtained by partitioning the elements of π into two sets. A balanced bipartition of π is a bipartition π 1 , π 2 such that 1 | π 1 | | π 2 | 1 , where | π i | ( i = 1 , 2 ) is denoted to the number of elements of | π i | . In this paper, let k and m be positive integers, we determine the values ψ m a x ( π ) and ψ m i n ( π ) of ( k , k 1 ) -biregular graphic sequence π = ( k m , ( k 1 ) m ) .

Keywords:Graph, Degree Sequence, ( k m , ( k 1 ) m ) -Biregular Graphic Sequence, Judicious Balanced Bipartition

(k, k − 1)-双正则可图序列的公平划分

李海燕,郭锦

海南大学信息科学技术学院,海南 海口

收稿日期:2018年4月11日;录用日期:2018年4月21日;发布日期:2018年4月28日

摘 要

π = ( d 1 , d 2 , , d n ) 是非负整数序列, π 1 , π 2 是将 π 的所有元素划分为两部分后的两个子序列。如果 1 | π 1 | | π 2 | 1 ,则称 π 1 , π 2 π 的一个平衡二部划分,其中 | π i | ( i = 1 , 2 ) 表示 π i 中的元素数目。设k和m是两个正整数, π = ( k m , ( k 1 ) m ) 是双正则可图序列。本文确定了 ψ m a x ( π ) 的值和 ψ m i n ( π ) 的值。

关键词 :图,度序列, ( k m , ( k 1 ) m ) -双正则可图序列,公平划分

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文中只限于讨论有限简单图。未给出的定义请参照文献 [1] 。设G和H是简单图,图 G + H 表示G与H的和,其顶点集为 V ( G + H ) = V ( G ) V ( H ) ,其边集为 E ( G + H ) = E ( G ) E ( H )

V 1 , V 2 是图G的一个二部划分,如果 1 | V 1 | | V 2 | 1 ,则称 V 1 , V 2 是G的一个二部平衡划分。对于 i = 1 , 2 e ( V i ) 表示两个端点都在 V i 中的边的数目, e ( V 1 , V 2 ) 表示两个端点分别在顶点子集 V 1 , V 2 中的边数。通常 e ( V 1 , V 2 ) 用来表示平衡二部划分的大小。图G的一个最大(最小)平衡二部划分 V 1 , V 2 是图G的所有平衡二部划分中 e ( V 1 , V 2 ) 的值达到最大(最小)。与最大,最小平衡划分问题不同,公平划分问题是寻找图G的一个划分,使得多个分量同时进行优化。

本文将把图的公平划分问题变形到度序列的公平划分问题。

若简单图有顶点集 v 1 , v 2 , , v n v i 的度为 d i ( i = 1 , , n ) ,则序列 π = ( d 1 , d 2 , , d n ) 称为G的度序列。记 N S n 为所有满足 n 1 d 1 d 2 d n 0 的整数序列的集合。如果π是某个n阶简单图G的度序列,那么称π为可图序列,且G为π的一个实现。记 G S n N S n 中的所有可图序列组成的集合。在可图度序列中, r n 表示有n个r,即度序列的实现中有n个顶点的度为r。

给定可图序列π, π 1 , π 2 是将π的元素划分为两部分后的两个子序列。如果 1 | π 1 | | π 2 | 1 ,则称 π 1 , π 2 是π的一个平衡二部划分,其中 | π i | ( i = 1 , 2 ) 表示 π i 中的元素数目。若G是π的一个实现, V 1 , V 2 是G的一个平衡二部划分且 V 1 , V 2 在π中的度序列分别为 π 1 , π 2 ,则称 V 1 , V 2 为π的平衡二部划分 π 1 , π 2 的一个实现。

类似于图的“公平”划分问题,我们考虑度序列的“公平”划分问题:寻找已知可图序列π的一个平衡二部划分 π 1 , π 2 ,使得 π 1 , π 2 的某个实现 V 1 , V 2 在π的所有平衡二部划分的所有实现下 min { e ( V 1 ) , e ( V 2 ) } 达到最大或者 max { e ( V 1 ) , e ( V 2 ) } 达到最小,记 ψ min ( π ) = min { e ( V 1 ) , e ( V 2 ) } ψ max ( π ) = max { e ( V 1 ) , e ( V 2 ) } 。若 V 1 , V 2 是π的某个平衡二部划分的一个实现,显然 ψ min ( π ) min { e ( V 1 ) , e ( V 2 ) } ψ max ( π ) max { e ( V 1 ) , e ( V 2 ) }

2. 主要定理及引理

定理2.1:(Erdös和Gallai [2] )设 π = ( d 1 , d 2 , , d n ) N S n i = 1 n d i 是偶数。则 π G S n 当且仅当对任意整数t,

i = 1 t d i t ( t 1 ) + j = t + 1 n min { d i , t } , 1 t n

都成立。

P : = ( p 1 , p 2 , , p m ) Q : = ( q 1 , q 2 , , q n ) 是两个非负整数序列。如果存在一个简单二部图 G [ X , Y ] 使得X和Y中的顶点度分别是 ( p 1 , p 2 , , p m ) ,那么称序列对是二部可图的,并称二部图的一个实现。Gale [3] 和Ryser [4] 分别独立地给出了关于二部可图序列的刻划定理。

定理2.2:(Gale [3] , Ryser [4] ) 设是两个非负整数序列且满足。若,则是二部可图的当且仅当

成立。

引理2.3:(Yin和Li [5] )设是偶数。如果,则

,若,则称π是-双正则可图的。本文主要给出双正则可图序列的公平划分的上下界。

3. (k, k − 1)-双正则可图序列的公平划分的上界

定理3.1:设是一个正整数,m是4的整数倍且。那么

1) 若,则

2) 若,则

证明:情形(1):

,那么是π的一个平衡二部

划分。这里,

(1)

(2)

接下来我们比较的大小。显然,由(1)和(2)得

,由(1)和(2)得,

可得

,由(1)和(2)得,

显然,

由定理2.2,是二部可图的。设的一个实现,则G也是的一个实现且是G的一个平衡二部划分。因此,

故,,且

情形(2):

。由于是偶数,所以的度和为偶数。由引理2.3知,。设的一个实现且

。令。容易验证G是π的一个实现,且

证毕。

4. (k, k-1)-双正则可图序列的公平划分的下界

定理4.1:设是一个正整数,m是4的整数倍且。那么

1) 若,则

2) 若,则

证明:情形(1):

,则是π的一个平衡二部划分。由于是偶数,所以的度和为偶数。又由引理2.3可得,。设的一个实现且

,令。容易验证G是π的一个实现,是G的一个平衡二部划分且

情形(2):。显然

。这里,

(3)

(4)

接下来我们比较的大小。显然,由(3)和(4)得

,由(3)和(4)得,

可知

,由(3)和(4)得,

显然,

由定理2.2,是二部可图的。设的一个实现,。令,则G是的一个实现且是G的一个平衡二部划分。故,

因此,。证毕。

基金项目

海南省自然科学基金(No. 20161003, 20161002);国家自然科学基金(No. 11601108)。

文章引用

李海燕,郭 锦. (k,k-1)-双正则可图序列的公平划分
Judicious Balanced Bipartitions of (k,k-1)-Biregular Graphic Degree Sequence[J]. 应用数学进展, 2018, 07(04): 423-428. https://doi.org/10.12677/AAM.2018.74053

参考文献

  1. 1. Bondy, J.A. and Murty, U.S.R. (1976) Graphy Theory with Applications. Macmillan Ltd Press, New York. https://doi.org/10.1007/978-1-349-03521-2

  2. 2. Erdös, P. and Gallai, T. (1960) Graphs with Prescribed Degrees of Vertices. Matematikai Lapok, 11, 264-274.

  3. 3. Gale, D. (1957) A Theorem on Flows in Networks. Pacific Journal of Mathematics, 7, 1073-1082. https://doi.org/10.2140/pjm.1957.7.1073

  4. 4. Ryser, H.J. (1957) Combinatorial Properties of Matrices of Zeros and Ones. Canadian Journal of Mathematics, 9, 371-377. https://doi.org/10.4153/CJM-1957-044-3

  5. 5. Yin, J.H. and Li, J.S. (2005) Two Sufficient Conditions for a Graphic Sequence to Have a Realization with Prescribed Clique Size. Discrete Mathematics, 301, 218-227. https://doi.org/10.1016/j.disc.2005.03.028

期刊菜单