北京大学期刊网　|　作者　　审稿人　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展 - 2018, Vol. 47(3): 373-382
 研究论文
 小直径二连通外平面图的彩虹连通数 Rainbow Connection Number of Biconnected Outerplanar Graphs with Small Diameters 邓兴超1, 宋贺2, 苏贵福3, 田润丽4 DENG Xingchao1,*, SONG He2,**, SU Guifu3, TIAN Runli4 1. 天津师范大学数学科学学院, 天津, 300387; 2. 南开大学数学科学学院, 教育部核心数学与组合数学重点实验室, 天津, 300071; 3. 北京化工大学理学院, 北京, 100029; 4. 中南林业科技大学理学院, 长沙, 湖南, 410004 1. College of Mathematical Science, Tianjin Normal University, Tianjin, 300387, P. R. China; 2. School of Mathematical Sciences, LPMC, Nankai University, Tianjin, 300071, P. R. China; 3. School of Science, Beijing University of Chemical Technology, Beijing, 100029, P. R. China; 4. College of Science, Central South University of Forestry and Technology, Changsha, Hunan, 410004, P. R. China 收稿日期: 2016-10-16 出版日期: 2018-06-08 2018, Vol. 47(3): 373-382 DOI: 10.11845/sxjz.2016123b
 PDF [339 KB] 3 下载 54 浏览 引用导出

Abstract：In this paper, we investigate rainbow connection number $\mathrm{rc}(G)$ of biconnected outerplanar graphs $G$ with diameter 2 or 3. We obtain the following results:If $G$ has diameter $2,$ then $\mathrm{rc}(G)=3$ for fan graphs $F_{n}$ with $n\geq 7$ or $C_5,$ otherwise $\mathrm{rc}(G)=2;$ if $G$ has diameter $3,$ then $\mathrm{rc}(G)\leq 4$ and the bound is sharp.
Key wordsrainbow connection number    rainbow coloring    diameter    outerplanar graph    maximal outerplanar graph
 PACS: O157.5

 [1] Beineke, L.W. and Pippert, R.E., A census of ball and disk dissections, In: Graph Theory and Applications (Alavi, Y., Lick, D.R. and White, A.T. eds.), Lecture Notes in Math., Vol. 303, Berlin: Springer-Verlag, 1972, 25-40.[2] Chandran, L.S., Das, A., Rajendraprasad, D. and Varma, N.M., Rainbow connection number and connected dominating sets,J. Graph Theory, 2012, 71(2): 206-218.[3] Chartrand, G. and Harary, F., Planar permutation graphs, Ann. Inst. Henri Poincaré Sect. B, 1967, 3: 433-438.[4] Chartrand, G., Johns, G.L., McKeon, K.A. and Zhang, P., Rainbow connection in graphs, Math. Bohem. 2008, 133: 85-98.[5] Deng, X.C., Xiang, K.N. and Wu, B. Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs, Appl. Math. Lett., 2012, 25(3): 237-244.[6] Dong, J.Y. and Li, X.L., Note on the rainbow connection numbers of graphs with diameter 2, 2011, arXiv: 1106.1258v2.[7] Huang, X.L., Li, X.L., Shi, Y.T., Yue, J. and Zhao, Y., Rainbow connections for outerplanar graphs with diameter 2 and 3,Appl. Math. Comput., 2014, 242: 277-280.[8] Lauri, J., Further hardness results on rainbow and strong rainbow connectivity, Discrete Appl. Math., 2016, 201: 191-200.[9] Li, H.Z., Li, X.L. and Liu, S.J., Rainbow connection of graphs with diameter 2, Discrete Math., 2012, 312(8): 1453-1457.[10] Li, X.L., Li, H.Z. and Sun, Y.F., Rainbow connection number of graphs with diameter 3, Discuss. Math. Graph Theory, 2017, 37: 141-154.[11] Uchizawa, K., Aoki, T., Ito, T., Suzuki, A. and Zhou, X., On the rainbow connectivity of graphs: complexity and FPT algorithms, Algorithmica, 2013, 67(2): 161-179.[12] West, D.B., Introduction to Graph Theory, 2nd Ed., Englewood Cliffs, NJ: Prentice Hall, 2001.
 [1] 单治超. 有限图上首达时等随机变量的极限定理[J]. 数学进展, 2016, 45(4): 481-490. [2] 刘端凤;黄元秋;. 直径为4的图的最大亏格[J]. 数学进展, 2009, 38(2): 185-191. [3] 郭曙光;徐光辉;陈永高;. 直径为d的n阶树的谱半径[J]. 数学进展, 2005, 34(6): 683-692.
Viewed
Full text

Abstract

Cited

Discussed