[1]李海燕,郭 锦.k-正则可图序列的公平划分问题[J].南京师范大学学报(自然科学版),2018,41(02):1.[doi:10.3969/j.issn.1001-4616.2018.02.001]
　Li Haiyan,Guo Jin.k-Regular Graphic Degree Sequence Variant of JudiciousBalanced Bipartition Problem of Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2018,41(02):1.[doi:10.3969/j.issn.1001-4616.2018.02.001]
点击复制

k-正则可图序列的公平划分问题()
分享到：

《南京师范大学学报》（自然科学版）[ISSN:1001-4616/CN:32-1239/N]

卷:
第41卷
期数:
2018年02期
页码:
1
栏目:
·数学与计算机科学·
出版日期:
2018-06-30

文章信息/Info

Title:
k-Regular Graphic Degree Sequence Variant of JudiciousBalanced Bipartition Problem of Graphs
文章编号:
1001-4616(2018)02-0001-07
作者:
李海燕; 郭 锦
海南大学信息科学技术学院,海南 海口 570228
Author(s):
Li Haiyan; Guo Jin
College of Information Science and Technology,Hainan University,Haikou 570228,China
关键词:
图; 度序列; k-正则可图序列; 平衡划分; 公平划分
Keywords:
graph; degree sequence; k-graphic sequence; balanced bipartition; judicious balanced bipartition
分类号:
O157.5
DOI:
10.3969/j.issn.1001-4616.2018.02.001
文献标志码:
A
摘要:
设π=(d1,d2,…,dn)是非负整数序列,π1,π2是将π的所有元素划分为两部分后的两个子序列. 如果-1≤|π1|-|π2|≤1,则称π1,π2是π的一个平衡二部划分,其中|πi|(i=1,2)表示πi中的元素数目. 设k和n是两个正整数,π=(kn)是k-正则可图序列. 本文确定了ψmax(π)的值和ψmin(π)的值.
Abstract:
Let π=(d1,d2,…,dn) be a graphic sequence of nonnegative integers and π1,π2 be 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) denote the number of elements of |πi|. In this paper,let k and n be positive integers,we determine the values ψmax(π) and ψmin(π) of k-regular graphic sequence π=(kn

参考文献/References:

[1] BONDY J A,MURTY U S R. Graphy theory with applications[M]. NewYork:Macmillan Ltd Press,1976.
[2]GAREY M R,JOHNSON D S,STOCKMEYER L J. Some simplified NP-completet graph proble-ms[J]. Theor Comput Sci,1976,1:237-267.
[3]KARPINSKI M. On approximability of minimum bisection problem[C]//Electronic Colloquium on Computational Complexity. Trier,Germany,2002.
[4]BOLLOBS B,SCOTT A D. Problems and results on judicious partitions[J]. Random Struct and Alg,2002,21:414-430.
[5]BOLLOBS B,SCOTT A D. Judicious partitions of graph[J]. Period Math Hungar,1993,26:125-137.[6]BOLLOBS B,SCOTT A D. Exact bounds for judicious partitions of graphs[J]. Combinatorica,1999,19:73-486.
[7]BOLLOBS B,SCOTT A D. Judicious partitions of bounded-degree graphs[J]. J graph theory,2004,46:131-143.
[8]XU B G,YAN J,YU X X. Balanced judicious bipartitions of graphs[J]. J graph theory,2010,63:210-225.
[9]XU B G,YAN J,YU X X. A note on balanced bipartitions[J]. Discrete Math,2010,310:2613-2617.
[10]XU B G,YU X X. Judicious k-partitions of graphs[J]. J combin theory Ser B,2009,99:324-337.
[11]XU B G,YU X X. Better bounds for k-partitions of graphs[J]. J combin theory Ser B,2009,99:324-337.
[11]XU B G,YU X X. Better bounds for rtitions of graphs[J]. Combinatorics,probability and computing,2011,20:631-640.
[12]XU B G,YU X X. On judicious bisections of graphs[J]. J combin theory Ser B,2014,106:30-69.
[13]ERD?S P,GALLAI T. Graphs with prescribed degrees of vertices[J]. Mat Lapok,1960,11:264-274.
[14]GALE D. A theorem on flows in networks[J]. Pacific J Math,1957,7:1073-1082.
[15]RYSER H J. Combinatorial properties of matrices of zeros and ones[J]. Canad J Math,1957,9:371-377.
[16]YIN J H,LI J S. Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size[J]. Discrete Math,2005,301:218-227.

相似文献/References:

[1]高岩波,任韩.独立数≤5的3-边连通简单图的上可嵌入性(英文)[J].南京师范大学学报(自然科学版),2006,29(01):17.
　Gao Yanbo~,Ren Han~.Upper Embeddability of 3-Edge-Connected Simple Graphs with Independence-Number≤5[J].Journal of Nanjing Normal University(Natural Science Edition),2006,29(02):17.
[2]徐爱庆.关于三类六点七边图的图设计[J].南京师范大学学报(自然科学版),2003,26(01):23.
　Xu Aiqing.The Designs of Three Kinds of Graphs with Six Points and Seven Edges[J].Journal of Nanjing Normal University(Natural Science Edition),2003,26(02):23.

备注/Memo

备注/Memo:
收稿日期:2018-01-16.
基金项目:海南省科协青年科技英才创新计划(QCXM201806).
通讯联系人:李海燕,博士,研究方向:图论. E-mail:lihaiyan@hainu.edu.cn
更新日期/Last Update: 2018-11-06