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

Academic Journal

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

Read the Article