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] Fei LEI,Fei WEN,Zepeng LI,Muchun LI. Vertex reducible edge coloring of the Lexicographic product of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(10): 107-114.
[2] Ziqiang FANG,Longjie LI,Haizhen REN. Spectra of product operation signed graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(10): 101-106.
[3] Yinzhen MEI,Huifeng FU. Sombor index on four operation graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 56-63.
[4] Li WANG,Jingwen LI,Wenzhu YANG,Huayan PEI. Adjacent vertex reducible total labeling of unicyclic graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 44-55.
[5] Kaiyang HU,Mingfang HUANG,Baolin MA. Vertex-distinguishing E-total coloring of complete bipartite graph K12, n for 12≤n≤88 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 36-43, 70.
[6] Yongjun WANG,Xiang CHEN. Vertex distinguishing general total colorings of complete 3-partite graphs by multisets [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 29-35.
[7] Hongyu CHEN. Linear arboricity in graphs of low treewidth [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 25-28, 35.
[8] Haicheng MA,Xiaojie YOU. Extremum of the matching maximum root of k-bridge graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 19-24.
[9] Ruiying XUE,Zongtian WEI,Meijuan ZHAI. Restricted burning connectivity of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 91-99, 109.
[10] Li ZHU,Peng LI,Aifa WANG. Study on semi-paired k-disjoint path cover of unit interval graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 80-90.
[11] Yanan SU,Chunling TONG,Yong LI,Senyuan SU. Equitable total coloring of generalized Petersen graphs P(n, k) [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 71-79.
[12] Chaofan LIANG,Fenjin LIU,Yuchao LI,Shunyi LIU. Construction of singularly cospectral graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 65-70.
[13] Yaxin SHI,Fengxia LIU,Hua CAI. On r-hued coloring of WnPm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 59-64.
[14] Jiaxin YUAN,Mingfang HUANG. Strong edge-coloring of graphs without K1, 3+ [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 53-58.
[15] Huan LIU,Huiying QIANG,Hongshen WANG,Yu BAI. 2-distance sum distinguishing coloring of trees [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 47-52, 58.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!