On the Strong Rainbow Connection of a Graph

July 2013
Asian Academy of Management Journal of Accounting & Finance;2013, Vol. 9 Issue 2, p299
Academic Journal
A path in an edge-colored graph, where adjacent edges may be colored the same, is a rainbow path if no two edges of it are colored the same. For any two vertices u and v of G, a rainbow u-v geodesic in G is a rainbow u-v path of length d(u, v), where d(u;v) is the distance between u and v. The graph G is strongly rainbow connected if there exists a rainbow u-v geodesic for any two vertices u and v in G. The strong rainbow connection number of G, denoted by src(G), is the minimum number of colors that are needed in order to make G strongly rainbow connected. In this paper, we first give a sharp upper bound for src(G) in terms of the number of edge-disjoint triangles in a graph G, and give a necessary and sufficient condition for the equality. We next investigate the graphs with large strong rainbow connection numbers. Chartrand et al. obtained that src(G) = m if and only if G is a tree, we will show that src(G) ≢ m-1, and characterize the graphs G with src(G) = m-2 where m is the number of edges of G.


Related Articles

  • The Removable Edges and the Contractible Subgraphs of 5-Connected Graphs. Qin, Chengfu; Guo, Xiaofeng; Ando, Kiyoshi // Graphs & Combinatorics;Jan2015, Vol. 31 Issue 1, p243 

    An edge of a k-connected graph G is said to be k-removable if G − e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction, that is, identification every component of H to a single vertex, results again a k-connected graph. In this paper,...

  • Triple Connected Domination Number of a Graph. Mahadevan, G.; Avadayappan, Selvam; Joseph, J. Paulraj; Subramanian, T. // International Journal of Mathematical Combinatorics;Jul2012, Vol. 3, p93 

    The concept of triple connected graphs with real life application was introduced in [7] by considering the existence of a path containing any three vertices of a graph G. In this paper, we introduce a new domination parameter, called Smarandachely triple connected domination number of a graph. A...

  • SELF CENTERED AND SELF MEDIAN INTUITIONISTIC FUZZY GRAPHS. Karunambigai, M. G.; Kalaivani, O. K. // Advances in Fuzzy Sets & Systems;Apr2013, Vol. 14 Issue 2, p101 

    In this paper, the concept of μstatus, minimum and maximum status of an IFG is defined. The definition of a self median intuitionistic fuzzy graph and the necessary and sufficient conditions for an IFG to be self median are given. Also, we discussed the relationship between self median IFG,...

  • On Two Variants of Rainbow Connection. Yuefang Sun // WSEAS Transactions on Mathematics;Mar2013, Vol. 12 Issue 3, p266 

    A vertex-colored graph G is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G...

  • The Connected Open Monophonic Number of a Graph. Santhakumaran, A. P.; Mahendran, M. // International Journal of Computer Applications;Oct2013, Vol. 80, p39 

    In this paper, we introduce and investigate the connected open monophonic sets and related parameters. For a connected graph G of order n, a subset S of vertices of G is a monophonic set of G if each vertex v in G lies on a x-y monophonic path for some elements x and y in S. The minimum...

  • Hyper Domination in Bipartite Semigraphs. Venkatakrishnan, Y. B.; Swaminathan, V. // WSEAS Transactions on Mathematics;Oct2012, Vol. 11 Issue 10, p866 

    Let S be a bipartite semigraph with NXa(y) ≥ 1 for every y ∈ Y . A vertex x ∈ X hyper dominates y ∈ Y if y ∈ Na(x) or y ∈ Na(NYa(x)). A subset D ⊆ X is a hyper dominating set of S if every y ∈ Y is hyper dominated by a vertex of D. A subset D ⊆ X...

  • On the bondage number of middle graphs. Aytaç, A.; Turaci, T.; Odabaş, Z. // Mathematical Notes;May2013, Vol. 93 Issue 5/6, p795 

    Let G = ( V ( G), E( G)) be a simple graph. A subset S of V ( G) is a dominating set of G if, for any vertex v ∈ V ( G) - S, there exists some vertex u ∈ S such that uv ∈ E( G). The domination number, denoted by γ( G), is the cardinality of a minimal dominating set of G. There...

  • ON THE MAXIMUM ORDERS OF AN INDUCED FOREST, AN INDUCED TREE, AND A STABLE SET. HERTZ, Alain; MARCOTTE, Odile; SCHINDL, David // Yugoslav Journal of Operations Research;2014, Vol. 24 Issue 2, p199 

    Let G be a connected graph, n the order of G, and f (resp. t) the maximum order of an induced forest (resp. tree) in G. We show that f - t is at most n - ⌈2√n - 1⌉. In the special case where n is of the form a² + 1 for some even integer a ≥ 4, f - t is at most n -...

  • On edge neighborhood graphs-II. Alsardary, Salar Y.; All, Ali A.; Balasubramanian, K. // Azerbaijan Journal of Mathematics;Jul2012, Vol. 2 Issue 2, p78 

    Let G be an undirected, simple, connected graph e and e = uv be an edge of G: Let NG(e) be the subgraph of G induced by the set of all vertices of G which are not incident to e but are adjacent to at least one end vertex of e. Ne is the class of all graphs H such that, for some graph G, NG(e)...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics