On Local-Strong Rainbow Connection Numbers On Generalized Prism Graphs And Generalized Antiprism Graphs

Eri Nugroho; Kiki Ariyanti Sugeng

doi:10.30598/pijmathvol1iss2pp43-58

Eri Nugroho Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Indonesia
Kiki Ariyanti Sugeng Universitas Indonesia

DOI: https://doi.org/10.30598/pijmathvol1iss2pp43-58

Keywords: Rainbow geodesic, d-local rainbow connection number, generalized prism graph, generalized antiprism graph

Abstract

Rainbow geodesic is the shortest path that connects two different vertices in graph such that every edge of the path has different colors. The strong rainbow connection number of a graph G, denoted by src(G), is the smallest number of colors required to color the edges of G such that there is a rainbow geodesic for each pair of vertices. The d-local strong rainbow connection number, denoted by lrscd, is the smallest number of colors required to color the edges of G such that any pair of vertices with a maximum distance d is connected by a rainbow geodesic. This paper contains some results of lrscd of generalized prism graphs (PmxCn) and generalized antiprism graphs for values of d=2, d=3, and d=4.

Downloads

Download data is not yet available.

References

G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, “Rainbow connection number of graphs,” Mathematica Bohemica, vol 133, pp. 85–98, 2008.

X. Li, and Y Sun, Rainbow Connections of Graphs. New York: Springer, 2012.

A. B. Ericksen, A matter of security, Graduating Engineer, and Computer Careers, pp. 24–28, 2007.

G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, “The rainbow connectivity of a graph,” Networks, vol. 54, no. 2, pp. 75-81, 2009.

G. Chartrand, F. Okamoto and P. Zhang, “Rainbow trees in graphs and generalized connectivity,” Networks, vol. 55, pp. 360-367, 2010.

M. Krivelevich and R. Yuster, “The rainbow connection of a graph is (at most) reciprocal to its minimum degree”, J. Graph Theory, vol. 63, no. 3, pp. 185-191, 2009.

Y. Sun, “On rainbow total-coloring of a graph,” Discrete Appl. Math., vol. 194, no. 304, pp. 171-177, 2015.

P. Dorbec, I. Schiermeyer, E. Sidorowicz and E. Sopena, “Rainbow connection in oriented graphs,” Discrete Appl. Math., vol. 179, pp. 69-78, 2014.

R. P. Carpentier, H. Liu, M. Silva and T. Sousa, “Rainbow connection for some families of hypergraphs,” Discrete Math., vol. 327, pp. 40-50, 2014.

X. Li and Y. Sun, “An updated survey of rainbow connections of graphs: a dynamic survey,” Theory and Applications of Graphs, 2017.

F. Septyanto and K. A. Sugeng, “Distance-Local Rainbow Connection Number,” Disussiones Mathematicae Graph Theory, 2020.

E. Nugroho and K. A. Sugeng, “Distance-Local Rainbow Connection Number on Prism Graph. Journal of Physics: Conference Series, vol. 1722, pp. 012-053, 2021.

M. I. Moussa and E. M. Badr, “Ladder and subdivision of ladder graphs with pendant edges are odd graceful,” International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks, vol. 8, no. 1, pp. 1-8, March, 2016.

U. Prajapati & S. Gajjar, “Prime Cordial Lebeling of Generalized Prism Graph,” Ultra Scientist, vol. 27, no 3A, pp. 189-204, 2015.

M. Baca, F. Bashir and A. Semanicova, “Face Antimagic Lebeling of Antiprism,” Util. Math, vol. 84, pp. 209-224, 2011.

R. N. Darmawan and D. Dafik, “Rainbow connection number of prism and product of two graphs,” Prosiding Seminar Matematika dan Pendidikan Matematik, vol. 1, no. 1, 2014.