THE RAINBOW VERTEX-CONNECTION NUMBERS OF WHEEL-SHIELD GRAPHS
Abstract
Let be a nontrivial simple connected graph, be an edge of and be an integer greater than or equal to . A path of order , denoted by , is a graph whose vertices can be labelled such that . A -shield graph is a graph obtained by and copies of such that the edge of -th embedded to -th edge of by embedding to and to . A path in a vertex-colored graph is said to be rainbow-vertex path if every internal vertex in the path has different color. A vertex-colored graph is said to be rainbow-vertex connected if for every pair of vertices there exists a rainbow-vertex path connecting them. The rainbow- vertex connection number of , denoted by , is the minimum colors needed to make rainbow-vertex connected. In this paper, we determine the rainbow-vertex connection numbers of of wheel-shield graphs , specifically finding that the number ranges from to depending on the order of the wheel.
Downloads
References
R. Sidabutar, “HASIL BELAJAR MATEMATIKA SISWA DITINJAU DARI KEBIASAAN BELAJAR DAN LINGKUNGAN BELAJAR,” Jurnal Pendidikan, vol. 19, no. 2, pp. 98–108, Dec. 2018.doi: https://doi.org/10.26740/jpeka.v2n1.p19-28
M. Mahfudhotin and R. Palupi, “THE SAMPLE SCHEDULING APPLICATION OF THE ANT COLONY OPTIMIZATION ALGORITHM IN VEHICLE ROUTING PROBLEM TO FIND THE SHORTEST ROUTE,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 18, no. 1, pp. 0643–0656, Mar. 2024, doi: https://doi.org/10.30598/barekengvol18iss1pp0643-0656.
M. E. Supiyandi, “PENERAPAN TEKNIK PEWARNAAN GRAPH PADA PENJADWALAN UJIAN DENGAN APPLICATION OF GRAPH COLORING TECHNIQUES IN SCHEDULING EXAMS WITH THE WELCH-POWELL ALGORITHM,” J. Ilmu Komput. dan Inform., vol. 03, no. 01, 2018.
Y. Yang, X. Wang, M. Song, J. Yuan, and D. Tao, “SPAGAN: SHORTEST PATH GRAPH ATTENTION NETWORK,” arXiv preprint arXiv:2101.03464, 2021.
Z. Song, H. Ma, S. Sun, Y. Xin, and R. Zhang, “RAINBOW: RELIABLE PERSONALLY IDENTIFIABLE INFORMATION RETRIEVAL ACROSS MULTI-CLOUD,” Cybersecurity, vol. 6, no. 1, p. 19, 2023.doi: https://doi.org/10.1186/s42400-023-00146-z
N. I. Yahya, A. Fatmawati, N. Nurwan, and S. K. Nasib, “RAINBOW VERTEX-CONNECTION NUMBER ON COMB PRODUCT OPERATION OF CYCLE GRAPH (C_4) AND COMPLETE BIPARTITE GRAPH (K_(3,N)),” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 17, no. 2, pp. 0673–0684, Jun. 2023, doi: https://doi.org/10.30598/barekengvol17iss2pp0673-0684
R. Diestel, GRAPH THEORY, 4th ed. New York: Springer, 2010.
R. M. Prihandini, R. Adawiyah, A. I. Kristiana, Dafik, A. Fatahillah, and E. R. Albirri, “SOME FAMILIES OF TREE ARE ELEGANT,” Advances in Mathematics: Scientific Journal, vol. 9, no. 12, pp. 10261–10266, 2020, doi: https://doi.org/10.37418/amsj.9.12.18.
Y. Peng, X. Lin, B. Choi, and B. He, “VCOLOR*: A PRACTICAL APPROACH FOR COLORING LARGE GRAPHS,” Front Comput Sci, vol. 15, p., 2021, doi: https://doi.org/10.1007/s11704-020-9205-y.
A. Silva, L. G. A. Rodriguez, and J. F. Filho, “THE IMPROVED COLOURANT ALGORITHM: A HYBRID ALGORITHM FOR SOLVING THE GRAPH COLOURING PROBLEM,” Int. J. Bio Inspired Comput., vol. 16, pp. 1–12, 2020, doi: https://doi.org/10.1504/IJBIC.2020.109000.
L. S. Chandran, D. Rajendraprasad, and M. Tesař, “RAINBOW COLOURING OF SPLIT GRAPHS,” Discrete Appl Math (1979), vol. 216, pp. 98–113, 2017.doi: https://doi.org/10.1016/j.dam.2015.05.021
E. Aigner-Horev and D. Hefetz, “RAINBOW HAMILTON CYCLES IN RANDOMLY COLORED RANDOMLY PERTURBED DENSE GRAPHS,” SIAM J. Discret. Math., vol. 35, pp. 1569–1577, 2020, doi: https://doi.org/10.1137/20M1332992.
K. Reda and D. Szafir, “RAINBOWS REVISITED: MODELING EFFECTIVE COLORMAP DESIGN FOR GRAPHICAL INFERENCE,” IEEE Trans Vis Comput Graph, vol. 27, pp. 1032–1042, 2020, doi: https://doi.org/10.1109/TVCG.2020.3030439.
D. N. S. Simamora and A. N. M. Salman, “THE RAINBOW (VERTEX) CONNECTION NUMBER OF PENCIL GRAPHS,” Procedia Comput Sci, vol. 74, pp. 138–142, 2015, doi: ttps://doi.org/10.1016/j.procs.2015.12.089.
R. Adawiyah, I. Agustin, R. Prihandini, R. Alfarisi, and E. Albirri, “ON THE LOCAL MULTISET DIMENSION OF GRAPH WITH HOMOGENOUS PENDANT EDGES ,” J. Phys. Conf. Ser, vol. 1538, no. 1, p. 012023, 2020.doi: https://doi.org/10.1088/1742-6596/1538/1/012023
R. Srinivasan and M. Vivekanandan, “ON PACKING COLOURING OF TRANSFORMATION OF PATH, CYCLE AND WHEEL GRAPHS,” Indian J Sci Technol, vol. 14, no. 23, pp. 1975–1981, Jun. 2021, doi: https://doi.org/10.17485/IJST/v14i23.606.
M. Krivelevich and R. Yuster, “THE RAINBOW CONNECTION OF A GRAPH IS (AT MOST) RECIPROCAL TO ITS MINIMUM DEGREE,” J Graph Theory, vol. 63, pp. 185–191, Apr. 2009, doi: https://doi.org/10.1002/jgt.20418
X. Li and S. Liu, “TIGHT UPPER BOUND OF THE RAINBOW VERTEX-CONNECTION NUMBER FOR 2-CONNECTED GRAPHS,” Discrete Appl Math (1979), vol. 173, pp. 62–69, 2014.doi: tps://doi.org/10.1016/j.dam.2014.04.002
S. Ismail, I. K. Hasan, T. Sigar, and S. K. Nasib, “RAINBOW CONNECTION NUMBER AND TOTAL RAINBOW CONNECTION NUMBER OF AMALGAMATION RESULTS DIAMOND GRAPH(〖BR〗_4) AND FAN GRAPH(F_3),” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 16, no. 1, pp. 023–030, Mar. 2022, doi: https://doi.org/10.30598/barekengvol16iss1pp023-030.
J. L. Gross, J. Yellen, and M. Anderson, GRAPH THEORY AND ITS APPLICATIONS. USA: CRC Press, 2018.
Copyright (c) 2025 Ratnaning Palupi, A.N.M. Salman
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
