JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2015, Vol. 50 ›› Issue (02): 27-31.doi: 10.6040/j.issn.1671-9352.0.2014.146

Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] LI Mei-lian, DENG Qing-ying. Maple calculation of the transition polynomial of plane graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 27-34.
[2] . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60.
[3] LIU Xiao-hua, MA Hai-cheng. Order of matching energy and Hosoya index of Q-shape graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 61-65.
[4] ZHANG Jiang-yue, XU Chang-qing. Linear 2-arboricity of graphs with maximum average degree at most 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(6): 7-10.
[5] CAO Ya-meng, LI Jiao, LI Guo-quan. On sumsets and translates of vector subspaces over finite fields [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(4): 7-10.
[6] CHEN Hong-yu, ZHANG Li. Linear 2-arboricity of planar graphs with 4-cycles have no common vertex [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 36-41.
[7] HE Yu-ping, WANG Zhi-wen, CHEN Xiang-en. Vertex-distinguishing total coloring of mC8 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(10): 24-30.
[8] LI Ting-ting, LAO Hui-xue. On the mean value of a hybrid arithmetic function [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 70-74.
[9] WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106.
[10] PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.
[11] CHEN Xiang-en, MIAO Ting-ting, WANG Zhi-wen. Vertex-distinguishing I-total colorings of the join of two paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 30-33.
[12] WANG Ye, SUN Lei. Every 1-planar graph without cycles of length 3 or 4 is 5-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 34-39.
[13] MA Hai-cheng, LI Sheng-gang. The digraphs representation of finite topologies [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 100-104.
[14] ZHU Xiao-ying, PANG Shi-you. On the maximal eccentric distance sum of tree with given domination number [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(2): 30-36.
[15] LI Fang, GUANG Ai-xia, LI Guo-quan. Sumsets and subsets of Bohr sets in finite abelian groups [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(2): 39-43.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!