紧优无向双环网络强彩虹连通数的下界估计

刘杰; 陈宝兴; 钟玮

doi:10.13471/j.cnki.acta.snus.2020A069

您当前的位置：

首页 >

文章列表页 >

紧优无向双环网络强彩虹连通数的下界估计

研究论文 | 更新时间：2023-11-01

- 紧优无向双环网络强彩虹连通数的下界估计
- A lower bound estimation about strong rainbow connectivity of optimal undirected double-loop networks
- 中山大学学报(自然科学版)(中英文) 2022年61卷第5期页码：159-164
- 作者机构：
  
  1.闽南师范大学计算机学院，福建漳州 363000
  2.三明医学科技职业学院，福建三明 365000
  3.福建省高等学校数据与智能应用重点实验室，福建漳州 363000
- 作者简介：
  
  刘杰（1973年生），男；研究方向：图论及其应用；E-mail：liusir5566@126.com
  陈宝兴（1961年生），男；研究方向：网络优化设计分析；E-mail：cbaoxing@126.com
- 基金信息：
  
  福建省高校科研专项项目(JK2017031);福建省中青年项目(JAT170361;JAT191506)
- DOI：10.13471/j.cnki.acta.snus.2020A069
  中图分类号： O157.5
- 纸质出版日期：2022-09-25，
  
  网络出版日期：2022-03-08，
  
  收稿日期：2020-12-01，
  
  录用日期：2021-04-02
扫描看全文
刘杰,陈宝兴,钟玮.紧优无向双环网络强彩虹连通数的下界估计[J].中山大学学报(自然科学版),2022,61(05):159-164.

LIU Jie,CHEN Baoxing,ZHONG Wei.A lower bound estimation about strong rainbow connectivity of optimal undirected double-loop networks[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2022,61(05):159-164.
刘杰,陈宝兴,钟玮.紧优无向双环网络强彩虹连通数的下界估计[J].中山大学学报(自然科学版),2022,61(05):159-164. DOI： 10.13471/j.cnki.acta.snus.2020A069.

LIU Jie,CHEN Baoxing,ZHONG Wei.A lower bound estimation about strong rainbow connectivity of optimal undirected double-loop networks[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2022,61(05):159-164. DOI： 10.13471/j.cnki.acta.snus.2020A069.

摘要

对无向双环网络最短路径唯一表示问题进行刻画，给出了紧优无向双环网络具有最短路径表示的一个充要条件。最后证明了一类具有唯一最短路径表示的紧优无向双环网络，其强彩虹连通数必大于或等于该网络的直径加1。

Abstract

The uniqueness of the shortest path representation of an undirected double-loop network is characterized，and a necessary and sufficient condition for an optimal undirected double-loop network which has the shortest path representation is given. Finally， it is proven that for a class of optimal undirected double-loop networks which have the shortest path representation， its strong rainbow connection number is greater than or equal to the diameter of the network plus 1.

关键词

无向双环网络最短路径彩虹路强彩虹连通数

Keywords

undirected double-loop networkthe shortest pathrainbow pathstrong rainbow connection number

references

CHARTRAND G， JOHNS G， MCKEON K， et al. Rainbow connection in graphs ［J］.Mathematica Bohemica， 2008， 133（1）： 85-98.

CHEN B X， MENG J X， XIAO W J. Some new optimal and suboptimal infinite families of undirected double-loop networks ［J］．Discrete Mathematics and Theoretical Computer Science， 2006， 8（1）： 299-312.

CHEN B X，MENG J X，XIAO W J. A diameter formula for an undirected double-loop network ［J］.Ars Combinatoria，2009， 90： 395-404.

李乔，徐俊明，张忠良．最优双环网络的无限族［J］.中国科学（A辑）， 1993， 23（9）： 979-992．

徐俊明，刘琦．一类 4 紧优双环网无限族［J］.中国科学（A辑）， 2003， 33（1）： 71-74．

陈协彬．步长有限制的双环网络的最优路由算法［J］．计算机学报， 2004， 27（5）： 596-603．

KRIVELEVICH M， YUSTER R. The rainbow connection of a graph is （at most） reciprocal to its minimum degree ［J］. Graph Theory， 2010， 63（3）： 185-191.

SCHIERMEYER I. Rainbow connection in graphs with minimum degree three ［C］//International Workshop on Combinatorial Algorithms， IWOCA， Hradec Nad Moravicí， Czech Republic，DBLP， 2009.

董九英，李学良. 图的彩虹连通数与最小度和［J］.中国科学（数学）， 2013， 43（1）： 7-14．

齐林明，苗连英，李卫奇. 关于边染色临界图的独立数［J］.华东师范大学学报（自然科学版）， 2015（1）： 114-119.

王燕，王建军．线性多边形链的彩虹路连通性［J］.数学进展， 2012， 41（4）： 418-422．

王万禹. 图的修正的彩虹顶点连通数［J］.山东大学学报（理学版）， 2015， 50（2）： 27-31.

赵燕，柴航. 三类特殊图的（强）彩虹连通数［J］.纯粹数学与应用数学， 2018， 34（3）： 309-315.

刘欣欣，陈宝兴，钟玮. 有向双环网络的彩虹路连通性［J］.厦门大学学报（自然科学版）， 2014， 53（6）： 787-791.

刘杰，陈宝兴. 无向双环网络的强彩虹连通性［J］.厦门大学学报（自然科学版）， 2019， 58（6）： 873-877.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据