TITLE

# On the Strong Rainbow Connection of a Graph

AUTHOR(S)
XUELIANG LI; YUEFANG SUN
PUB. DATE
July 2013
SOURCE
Asian Academy of Management Journal of Accounting & Finance;2013, Vol. 9 Issue 2, p299
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
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.
ACCESSION #
88053840

## 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)...

Share