区间上二部可图序列刻划定理的推广

2016-05-06 06:11:44郭纪云蔡白光
长沙大学学报 2016年2期
关键词:关联

郭纪云,蔡白光

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



区间上二部可图序列刻划定理的推广

郭纪云,蔡白光

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

摘要:设Pm=p1,…,pm及Qn=q1,…,qn是两个由非负整数构成的不增序列. 如果存在一个简单X,Y-二部图G使得X中的顶点的度分别为p1,…,pm且Y中的顶点的度分别为q1,…,qn,那么称序列对(Pm,Qn)是二部可图的, 并称二部图G为(Pm,Qn)的一个实现. 如果(Pm,Qn)二部可图且任何两个来自不同部集的顶点之间最多关联t条边,那么称(Pm,Qn)是t-二部可图的, 并称(Pm,Qn)的实现为t-二部图. Gale和Ryser分别独立地给出了关于二部可图序列的刻划定理. Garg等人考虑了区间上的二部可图序列,并给出相应刻划. 此研究将其刻划由1-二部推广至图t-二部图.

关键词:二部可图序列;区间上二部可图序列; t-二部可图序列

1相关知识

设Pm=p1,…,pm及Qn=q1,…,qn是两个由非负整数构成的不增序列. 如果存在一个简单X,Y-二部图G使得X中的顶点的度分别为p1,…,pm且Y中的顶点的度分别为q1,…,qn,那么称序列对(Pm,Qn)是二部可图的, 并称二部图G为(Pm,Qn)的一个实现. Gale[1]和Ryser[2]分别给出了经典的关于二部可图序列的刻划定理.Garg等人[3]则考虑了区间上的二部可图序列,并给出如下定理.

称由非负整数构成的不增序列对(Pm,Qn)是t-二部可图的, 如果(Pm,Qn)二部可图且任何两个来自不同部集的顶点之间最多关联t条边. 此时, (Pm,Qn)的实现称为t-二部图.本文给出一个区间上t-二部可图序列刻划定理, 从而将区间上二部可图序列的刻划从1-图推广至t-图.

定理1.2设L1=([a1,b1],…,[am,bm])和L2=([c1,d1],…,[cn,dn])是两个由非负整数构成的区……

登录APP查看全文

猜你喜欢
关联
不惧于新,不困于形——一道函数“关联”题的剖析与拓展
“苦”的关联
当代陕西(2021年17期)2021-11-06 03:21:36
船山与宋学关联的再探讨
原道(2020年2期)2020-12-21 05:47:06
“一带一路”递进,关联民生更紧
当代陕西(2019年15期)2019-09-02 01:52:00
新制度关联、组织控制与社会组织的倡导行为
奇趣搭配
基于广义关联聚类图的分层关联多目标跟踪
自动化学报(2017年1期)2017-03-11 17:31:17
智趣
读者(2017年5期)2017-02-15 18:04:18
探讨藏医学与因明学之间的关联
西藏科技(2016年5期)2016-09-26 12:16:39
GPS异常监测数据的关联负选择分步识别算法