Rainbow vertex connection number and strong rainbow vertex connection number on slinky graph (SlnC4))

Afifah Farhanah Akadji, Muhammad Rifai Katili, Salmun K. Nasib, Nisky Imansyah Yahya

Abstract


A graph is said rainbow connected if no path has more than one vertices of the same color inside. The minimum number of colors required to make a graph to be rainbow vertex-connected is called rainbow vertex connection-number and denoted by rvc(G) . Meanwhile, the minimum number of colors  required to make a graph to be strongly rainbow vertex-connected is called strong rainbow vertex connection-number and denoted by srvc(G). Suppose there is a simple, limited, and finite graph G. Thus, G=(V(G),E(G)) with the determination of k-coloring c:V(G)->{1,2,...,k} . The reaserch aims at determining rainbow vertex connection-number and strong rainbow vertex connection-number on slinky graphs (Sl_nC_4). Moreover, the research method applies a literature study with the following procedures; drawing slinky graphs (Sl_nC_4), looking for patterns of rainbow vertex connection-number, and strong rainbow vertex connection-number on slinky graphs (Sl_nC_4), then proving the theorems obtained from the previous pattern. It is obtained rvc(Sl_nC_4)=2n-1, srvc(Sl_2C_4)=4, and srvc(Sl_nC_4) = 3n-3 for n>= 3. 


Keywords


Graph; Slinky Graph; Rainbow Vertex Connection; Strong Rainbow Vertex Connection

Full Text:

PDF

References


Balakrishnan, R., & Ranganathan, K. (2012). A textbook of graph theory. In Journal of Chemical Information and Modeling (2nd ed, Vol. 53, Issue 9). Springer.

Budayasa, I. K. (2007). Graph theory and its application. Unesa University Press.

Bustan, A. W. (2016). Bilangan terhubung titik pelangi untuk graf lingkaran bintang (𝑺𝒎𝑪𝒏). BAREKENG: Jurnal Ilmu Matematika Dan Terapan, 10(2). https://doi.org/10.30598/barekengvol10iss2pp77-81

Bustan, A. W. (2019). Rainbow vertex connection number of several G-star graphs. Institut Teknologi Bandung.

Bustan, A. W., & Salman, A. N. M. (2018). The rainbow vertex-connection number of star fan graphs. CAUCHY, 5(3). https://doi.org/10.18860/ca.v5i3.5516

Chartrand, G., Johns, G. L., McKeon, K. A., & Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1). https://doi.org/10.21136/mb.2008.133947

Chartrand, G., & Zhang, P. (2012). A first course in graph theory. Dover Publication, INC.

Chen, L., Li, X., Liu, H., & Liu, J. (2018). On various (strong) rainbow connection numbers of graphs. Australasian Journal of Combinatorics, 70(1).

Coxeter, H. S. M. (1971). The mathematics of map coloring. Leonardo, 4(3). https://doi.org/10.2307/1572306

Dafik, Slamin, & Muharromah, A. (2018). On the (strong) rainbow vertex connection of graphs resulting from edge comb product. Journal of Physics: Conference Series, 1008(1). https://doi.org/10.1088/1742-6596/1008/1/012055

Krivelevich, M., & Yuster, R. (2010). The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3). https://doi.org/10.1002/jgt.20418

Li, X., Mao, Y., & Shi, Y. (2014). The strong rainbow vertex-connection of graphs. Utilitas Mathematica, 93.

Ummah, W. (2013). Graph labelling. https://www.academia.edu/4306800/PELABELAN_GRAF

Vasudev, C. (2006). Graph theory with applications. New Age International.

Wibisono, S. (2008). Discrete mathematics (2nd ed.; A). Graha Ilmu.




DOI: http://dx.doi.org/10.24042/djm.v4i2.7276

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 Desimal: Jurnal Matematika

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

  Creative Commons License
Desimal: Jurnal Matematika is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.