Rainbow connection number of Connected
Graph

Dr. Maneesha Sakalle; Richa Jain

doi:https://doi.org/10.14445/22315373/IJMTT-V33P522

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 33 | Number 3 | Year 2016 | Article Id. IJMTT-V33P522 | DOI : https://doi.org/10.14445/22315373/IJMTT-V33P522

Rainbow connection number of Connected Graph

Dr. Maneesha Sakalle, Richa Jain

Abstract

A path of a connected graph is rainbow if no two edges of it are colored the same. An edge-coloring graph is rainbow connected if a rainbow path connects any two vertices. An edge coloring under which is rainbow connected is called a rainbow coloring. The rainbow connection number of a connected graph , denoted by , as the smallest number of colors that are needed in order to make rainbow connected. In this paper, we construct different type of connected graph and determine the exact value of for them.

Keywords

In this paper, we construct different type of connected graph and determine the exact value of for them.

References

[1] D. Dellamonica Jr., C. Magnant and D.M. Martin, Rainbow Paths, Discrete Math. 310(4), 774-781(2010).
[2] E.S. Elmallah and C.J. Colbourn, Series-parallel subgraphs of Planar Graphs, Networks 22(6), 607-614(1992).
[3] G. Chartrand, F. Okamoto and P. Zhang, Rainbow Trees in Graphs and Generalized Connectivity, Networks 55(4),360-367,(2010).
[4] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang , Rainbow Connection in Graphs, Math. Bohem, 133(1), 85-98, (2008).
[5] G. Chartrand, P. Zhang, Introduction to Graph Theory. Macraw-Hill, Boston, (2011). [6] M. Krivelevich, R. Yuster, The Rainbow Connection of a Graph is (atmost) Reciprocal to its Minimum Degree, J. Graph Theory 63(3) , 185- 191, (2009).
[7] M. K. Angel Jebitha Domination Uniform Subdivision Number of Graph, International Journal of Mathematics Trends and Technology-(27),( 2015)
[8] Prabhanjan Ananth, Meghana Nasre and Kanthi K. Sarpatwar, Hardness and Parameterized Algorithms on Rainbow Connectivity Problem, CoRR, abs/1105.0979, (2011).
[9] Rod G. Downey and M.R. Fellows, Parameterized Complexity, Monographs in Computer Science, Springer, (1999).
[10] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and Algorithms for Rainbow Connection, 26th International Symposium on Theoretical Aspects on Computer Science STACS 2009(2009) 243-254. Also, see Journal of Combinatorial Optimization, 21, 330-347(2011).
[11] X. Li, Y. Sun, Rainbow Connections of Graphs-A survey, available at http://arxive.org/abs/1101.5747(2011).
[12] Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On Rainbow Connection, The Electronic Journal of Combinatorics, 15(R57): 1, (2008).

Citation :

Dr. Maneesha Sakalle, Richa Jain, "Rainbow connection number of Connected Graph," International Journal of Mathematics Trends and Technology (IJMTT), vol. 33, no. 3, pp. 156-160, 2016. Crossref, https://doi.org/10.14445/22315373/IJMTT-V33P522