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

期刊菜单

(k,k-1)-双正则可图序列的公平划分
Judicious Balanced Bipartitions of (k,k-1)-Biregular Graphic Degree Sequence

DOI:10.12677/AAM.2018.74053,PDF,HTML,XML,下载: 1,654浏览: 2,979国家自然科学基金支持
作者:李海燕,郭锦：海南大学信息科学技术学院，海南海口
关键词:图；度序列；(km；(k-1)m)-双正则可图序列；公平划分；Graph；Degree Sequence；(km；(k-1)m)-Biregular Graphic Sequence；Judicious Balanced Bipartition

摘要: 设π= （d₁,d₂,…,d_n）是非负整数序列，π₁,π₂是将π的所有元素划分为两部分后的两个子序列。如果-1≤|π₁|-| π₂|≤1，则称π₁π₂是π的一个平衡二部划分，其中|π_i|(i=1,2)表示 π_i中的元素数目。设k和m是两个正整数，π= (k^m,(k-1)^m)是双正则可图序列。本文确定了 Ψ_max(π)的值和Ψ_min(π)的值。。

Abstract:Let π= （d ₁,d ₂,…,d _nbe a graphic sequence of nonnegative integers and π ₁,π ₂are two sequences that are obtained by partitioning the elements of π into two sets. A balanced bipartition of π is a bipartition π ₁,π ₂such that -1≤|π ₁|-| π ₂|≤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 Ψ _max(π) and Ψ _min(π) of (k,k-1)-biregular graphic sequence π= (k ^m,(k-1) ^m).

文章引用：李海燕, 郭锦. (k,k-1)-双正则可图序列的公平划分[J]. 应用数学进展, 2018, 7(4): 423-428. https://doi.org/10.12677/AAM.2018.74053

1. 引言

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

设 $V_{1}, V_{2}$ 是图G的一个二部划分，如果 $- 1 \leq | V_{1} | - | V_{2} | \leq 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}, \dots, v_{n}$ 且 $v_{i}$ 的度为 $d_{i} (i = 1, \dots, n)$ ，则序列 $π = (d_{1}, d_{2}, \dots, d_{n})$ 称为G的度序列。记 $N S_{n}$ 为所有满足 $n - 1 \geq d_{1} \geq d_{2} \geq \dots \geq d_{n} \geq 0$ 的整数序列的集合。如果π是某个n阶简单图G的度序列，那么称π为可图序列，且G为π的一个实现。记 $G S_{n}$ 为 $N S_{n}$ 中的所有可图序列组成的集合。在可图度序列中， $r^{n}$ 表示有n个r，即度序列的实现中有n个顶点的度为r。

给定可图序列π, $π_{1}, π_{2}$ 是将π的元素划分为两部分后的两个子序列。如果 $- 1 \leq | π_{1} | - | π_{2} | \leq 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} (π) \geq \min {e ({V^{'}}_{1}), e ({V^{'}}_{2})}$ ， $ψ_{\max} (π) \leq \max {e ({V^{'}}_{1}), e ({V^{'}}_{2})}$ 。

2. 主要定理及引理

定理2.1：(Erdös和Gallai [2] )设 $π = (d_{1}, d_{2}, \dots, d_{n}) \in N S_{n}$ 且 $\sum_{i = 1}^{n} d_{i}$ 是偶数。则 $π \in G S_{n}$ 当且仅当对任意整数t，

$\sum_{i = 1}^{t} d_{i} \leq t (t - 1) + \sum_{j = t + 1}^{n} \min {d_{i}, t}, 1 \leq t \leq n$

都成立。

设 $P : = (p_{1}, p_{2}, \dots, p_{m})$ ， $Q : = (q_{1}, q_{2}, \dots, q_{n})$ 是两个非负整数序列。如果存在一个简单二部图 $G [X, Y]$ 使得X和Y中的顶点度分别是 $(p_{1}, p_{2}, \dots, 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)。

参考文献

[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]	Erdös, P. and Gallai, T. (1960) Graphs with Prescribed Degrees of Vertices. Matematikai Lapok, 11, 264-274.
[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]	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]	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

为你推荐

友情链接