Please wait a minute...
北京大学期刊网 | 作者  审稿人  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 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]
1
下载
30
浏览

引用导出
E-mail这篇文章
E-mail提醒
RSS订阅

摘要 本文研究直径为2或3的二连通外平面图$G$的彩虹连通数$\mathrm{rc}(G)$, 得到如下结果: 如果$G$的直径为2, 则对扇形图$F_n$ $(n\geq7)$或$C_5$有$\mathrm{rc}(G)=3$, 否则$\mathrm{rc}(G)=2$; 如果$G$的直径为3, 则$\mathrm{rc}(G)\leq4$并且这个界是紧的.
关键词 彩虹连通数彩虹着色直径外平面图极大外平面图    
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  
通讯作者: E-mail: $*$ dengyuqiu1980@126.com; $**$ songhe@mail.nankai.edu.cn   
[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   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .