您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

山东大学学报(理学版) ›› 2015, Vol. 50 ›› Issue (02): 27-31.doi: 10.6040/j.issn.1671-9352.0.2014.146

• 论文 • 上一篇    下一篇

图的修正的彩虹顶点连通数

王万禹   

  1. 成都师范学院数学系, 四川 成都 611130
  • 收稿日期:2014-04-10 修回日期:2014-10-14 出版日期:2015-02-20 发布日期:2015-01-27
  • 作者简介:王万禹(1986-), 男, 硕士, 讲师,研究方向为图论及其应用. E-mail: wangwangu198616@163.com
  • 基金资助:
    四川省教育厅自然科学基金(14ZB0329); 成都师范学院科研基金项目(CS14ZB06)

Revised rainbow vertex-connection number of graphs

WANG Wan-yu   

  1. Department of Mathematics, Chengdu Normal University, Chengdu 611130, Sichuan, China
  • Received:2014-04-10 Revised:2014-10-14 Online:2015-02-20 Published:2015-01-27

摘要: G称为是修正的强彩虹顶点连通的,如果对于G的任意两个顶点u, v, G都有一条修正的彩虹u-v测地线. 使图G是修正的强彩虹顶点连通图的最小颜色数目k称为图G的修正的强彩虹连通数, 记做srvc*(G).文中给出了Cn的修正的顶点彩虹连通数,rvc*(Cn)=, n≥4. 给出了含t个边不交三角的图的修正的强彩虹顶点连通数的一个上界.

关键词: 修正的强彩虹顶点连通性, 彩虹顶点着色, 修正的彩虹顶点连通性

Abstract: If for every pair u, v of distinct vertices, G contains a revised rainbow u-v geodesic, then G is revised strong vertex-connected. The minimum number k for which there exists a k-vertex-coloring of G that results in a revised strong rainbow vertex-connected graph is called the revised strong rainbow vertex-connection number of G, denoted by srvc*(G). Then rvc*(Cn)= for n≥4 is proved, and a upper bound is given for the revised strong rainbow connection number of graphs depending on the the number of edge-disjoint triangles.

Key words: revised rainbow vertex-connection, revised strong rainbow vertex-connection, rainbow vertex-coloring

中图分类号: 

  • O157
[1] KRIVELEVICH M, YUSTER R. The Rainbow connection of a graph is (at most) reciprocal to its minimum degree[J]. J Graph Theory, 2010, 63(3):185-191.
[2] CHEN Lili, LI Xueliang, SHI Yongtang. The complexity of determining the rainbow vertex-connection of a graph[J]. Theoret Comput Sci, 2011, 12(35):4531-4535.
[3] CHARTRAND G, JOHNS G L, MCKEON K A. Rainbow connection in graphs[J]. Math Bohem, 2008, 133:85-98.
[4] CARO Y, LEV A, RODITTY V. On rainbow connection[J/OL]. Electron J Combin, 2008,15:R57. http://www.researchgate.net/publication/220342507_On_Rainbow_Connection.
[5] LI Xueliang, SHI Yongtang, SUN Yuefang. Rainbow connections of a graphs: A survey[J]. Graph & Combin, 2013, 29:1-38.
[6] SCHIERMEYER I. Rainbow connection in graphs with minimum degree three[M]// IWOCA 2009, LNCS 5847. Berlin Heidelberg: Springer, 2009: 432-437.
[7] LI Xueliang, SUN Yuefang. Rainbow connection numbers of line graphs[J]. Ars Combin, 2011, 100:449-463.
[8] LI Xueliang, LIU Sujuan. Tight upper bound of the rainbow vertex-connection number for 2-connected graphs[J]. Discrete Applied Mathematics, 2014, 173:62-69.
[1] 李美莲,邓青英. 平图的transition多项式的Maple计算[J]. 山东大学学报(理学版), 2018, 53(10): 27-34.
[2] 寇艳芳,陈祥恩,王治文. K1,3,p K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报(理学版), 2018, 53(8): 53-60.
[3] 刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报(理学版), 2018, 53(8): 61-65.
[4] 张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报(理学版), 2018, 53(6): 7-10.
[5] 曹亚萌,黎娇,李国全. 有限域上的和集与子空间的平移[J]. 山东大学学报(理学版), 2018, 53(4): 7-10.
[6] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2017, 52(12): 36-41.
[7] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报(理学版), 2017, 52(10): 24-30.
[8] 李亭亭,劳会学. 一类混合型数论函数的均值估计[J]. 山东大学学报(理学版), 2017, 52(8): 70-74.
[9] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报(理学版), 2017, 52(8): 100-106.
[10] 潘文华,徐常青. 一类稀疏图的邻和可区别边色数[J]. 山东大学学报(理学版), 2017, 52(8): 94-99.
[11] 陈祥恩,苗婷婷,王治文. 两条路的联图的点可区别I-全染色[J]. 山东大学学报(理学版), 2017, 52(4): 30-33.
[12] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报(理学版), 2017, 52(4): 34-39.
[13] 马海成,李生刚. 有限拓扑的有向图表示[J]. 山东大学学报(理学版), 2017, 52(4): 100-104.
[14] 朱晓颖,逄世友. 控制数给定的树的最大离心距离和[J]. 山东大学学报(理学版), 2017, 52(2): 30-36.
[15] 李芳,关爱霞,李国全. 有限Abel群中的和集与Bohr集的子集[J]. 山东大学学报(理学版), 2017, 52(2): 39-43.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!