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.
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.
A lower bound estimation about strong rainbow connectivity of optimal undirected double-loop networks
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.
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.