您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 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

PDF (PC)

909

被引次数

1

摘要： 图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] 雷飞,文飞,李泽鹏,李沐春. 图的字典积的点可约边染色[J]. 《山东大学学报(理学版)》, 2024, 59(10): 107-114.
[2] 方子强,李龙捷,任海珍. 积运算符号图的谱[J]. 《山东大学学报(理学版)》, 2024, 59(10): 101-106.
[3] 梅银珍,符惠芬. 四类运算图的Sombor指数[J]. 《山东大学学报(理学版)》, 2024, 59(6): 56-63.
[4] 王丽,李敬文,杨文珠,裴华艳. 单圈图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2024, 59(6): 44-55.
[5] 胡开洋,黄明芳,马宝林. 完全二部图K12, n(12≤n≤88)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 36-43, 70.
[6] 王勇军,陈祥恩. 完全三部图的点被多重集可区别的一般全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 29-35.
[7] 陈宏宇. 树宽较小的图的线性荫度[J]. 《山东大学学报(理学版)》, 2024, 59(6): 25-28, 35.
[8] 马海成,攸晓杰. k-桥图匹配最大根的极值[J]. 《山东大学学报(理学版)》, 2024, 59(6): 19-24.
[9] 薛睿滢,魏宗田,翟美娟. 图的限制性燃烧连通度[J]. 《山东大学学报(理学版)》, 2024, 59(2): 91-99, 109.
[10] 朱莉,李鹏,王爱法. 单位区间图的半配对k-不相交路覆盖研究[J]. 《山东大学学报(理学版)》, 2024, 59(2): 80-90.
[11] 苏亚男,仝春灵,李勇,苏森原. 广义Petersen图P（n, k）的等全着色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 71-79.
[12] 梁超凡,刘奋进,李玉超,柳顺义. 奇异同谱图的构造[J]. 《山东大学学报(理学版)》, 2024, 59(2): 65-70.
[13] 史雅馨,刘凤霞,蔡华. Wn□Pm的r-hued染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 59-64.
[14] 袁佳鑫,黄明芳. 不含K1, 3+图的强边染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 53-58.
[15] 刘欢,强会英,王洪申,白羽. 树图的2-距离和可区别染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 47-52, 58.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发