DIGRUNDY NUMBER OF DIRECTED STAR, BANANA TREE, FIREWORKS, AND COCONUT TREE GRAPHS
Abstract
A digrundy coloring of a graph is a vertex coloring in which every vertex assigned a higher color is adjacent to vertices assigned all smaller colors. The maximum number of colors that can be realized in such a coloring of an acyclic directed graph is called the digrundy number. This paper determines the digrundy numbers of several classes of acyclic directed graphs, namely directed star graphs, directed banana tree graphs, directed fireworks graphs, and directed coconut tree graphs. The analysis is based on structural properties of the graphs and combinatorial arguments derived from digrundy coloring constraints. The results show that the digrundy number of directed star graphs is under orientations where the central vertex satisfies and . For directed banana tree graphs with a specified orientation , the digrundy number is for and for . Under arbitrary orientations, directed fireworks graphs have digrundy number , while for directed coconut tree graphs , the digrundy number is bounded by These findings provide exact values of the digrundy number for the graph classes considered and highlight the role of structural constraints in governing digrundy coloring behavior.
Downloads
References
M. Aslan, “A PERFORMANCE COMPARISON OF GRAPH COLORING ALGORITHMS,” Int. J. Intell. Syst. Appl. Eng., vol. 4, no. Special Issue-1, pp. 1–7, Dec. 2016. doi: https://doi.org/10.18201/ijisae.273053.
K. R. Saoub, GRAPH THEORY: AN INTRODUCTION TO PROOFS, ALGORITHMS, AND APPLICATIONS, 1st ed. in Textbooks in mathematics. Boca Raton: CRC Press, 2021. doi: https://doi.org/10.1201/9781138361416.
I. Gutman, V. R. Kulli, and I. R. zepovic, “IRREGULARITY SOMBOR INDEX,” Bull. Acad. Sci. Arts Repub. Serbia Cl. Math. Nat. Sci., vol. 156, pp. 31–37, 2023, doi: 10.5281/zenodo.18005956.
F. Susanto, R. Simanjuntak, and E. T. Baskoro, “FURTHER RESULTS ON THE TOTAL VERTEX IRREGULARITY STRENGTH OF TREES,” Electron. J. Graph Theory Appl., vol. 13, no. 1, p. 123, Apr. 2025. doi: https://doi.org/10.1201/9781138361416.
S. Wagner and H. Wang, INTRODUCTION TO CHEMICAL GRAPH THEORY. Boca Raton: CRC Press, Taylor & Francis Group, 2018. doi: https://zenodo.org/doi/10.5281/zenodo.17785567.
V. Zverovich, MODERN APPLICATIONS OF GRAPH THEORY, 1st ed. Oxford: Oxford university press, 2021. doi: https://doi.org/10.1093/oso/9780198856740.001.0001.
G. Ali, M. Bača, M. Lascsáková, A. Semaničová-Feňovčíková, A. ALoqaily, and N. Mlaiki, “MODULAR TOTAL VERTEX IRREGULARITY STRENGTH OF GRAPHS,” AIMS Math., vol. 8, no. 4, pp. 7662–7671, 2023. doi: https://doi.org/10.3934/math.2023384.
V. Aparna, N. Mohanapriya, and S. Broumi, “SINGLE VALUED NEUTROSOPHIC R-DYNAMIC VERTEX COLORING OF GRAPHS,” Neutrosophic Sets Syst., vol. 48, pp. 306–317, 2022.
J. Lin, “A REDUCTION BASED METHOD FOR COLORING VERY LARGE GRAPHS,” Int. Jt. Conf. Artif. Intell., pp. 517–523, 2017. doi: https://doi.org/10.24963/ijcai.2017/73.
Md. S. Rahman, BASIC GRAPH THEORY. IN UNDERGRADUATE TOPICS IN COMPUTER SCIENCE. Cham: Springer International Publishing, 2017. doi: https://doi.org/10.1007/978-3-319-49475-3.
R. Diestel, GRAPH THEORY, 5TH ED. IN GRADUATE TEXTS IN MATHEMATICS. Berlin, Heidelberg: Springer Berlin Heidelberg, 2017. doi: https://doi.org/10.1007/978-3-662-53622-3
S. D. Pasham, “NETWORK TOPOLOGY OPTIMIZATION IN CLOUD SYSTEMS USING ADVANCED GRAPH COLORING ALGORITHMS,” Res. Anal. J., vol. 6, no. 11, pp. 01–25, 2023. doi: https://doi.org/10.18535/raj.v6i11.426.
Z. Dvořák and L. Postle, “CORRESPONDENCE COLORING AND ITS APPLICATION TO LIST-COLORING PLANAR GRAPHS WITHOUT CYCLES OF LENGTHS 4 TO 8,” J. Comb. Theory Ser. B, vol. 129, pp. 38–54, 2018. doi: https://doi.org/10.1016/j.jctb.2017.09.001.
D. Cardoso, O. Cerdeira, C. Dominicc, and P. Cruz, “INJECTIVE EDGE COLORING OF GRAPHS,” Filomat, vol. 33, no. 19, pp. 6411–6423, 2019. doi: https://doi.org/10.2298/FIL1919411C.
S. Jahanbekam, J. Kim, S. O, and D. B. West, “ON R-DYNAMIC COLORING OF GRAPHS,” Discrete Appl. Math., vol. 206, pp. 65–72, 2016. doi: https://doi.org/10.1016/j.dam.2016.01.016.
E. Andrews, D. Johnston, and P. Zhang, “ON TWIN EDGE COLORINGS IN TREES,” J Comb. Math Comb. Comput, vol. 94, pp. 115–131, 2015.
N. Kusumastuti, Raventino, and F. Fran, “THE DIACHROMATIC NUMBER OF DOUBLE STAR GRAPH,” J. Phys. Conf. Ser., vol. 2106, no. 1, p. 012024, Nov. 2021. doi: https://doi.org/10.1088/1742-6596/2106/1/012024.
G. Araujo-Pardo, J. J. Montellano-Ballesteros, M. Olsen, and C. Rubio-Montiel, “THE DIGRUNDY NUMBER OF DIGRAPHS,” Discrete Appl. Math., vol. 317, pp. 117–123, 2022. doi: https://doi.org/10.1016/j.dam.2022.04.005.
B. Effantin, U. de Lyon, and U. Lyon, “A NOTE ON GRUNDY COLORINGS OF CENTRAL GRAPHS,” Australas. J. Comb., vol. 68, no. 3, pp. 346–356, 2017.
É. Bonnet, F. Foucaud, E. J. Kim, and F. Sikora, “COMPLEXITY OF GRUNDY COLORING AND ITS VARIANTS,” Discrete Appl. Math., vol. 243, pp. 99–114, 2018. doi: https://doi.org/10.1016/j.dam.2017.12.022.
T. Fujita, “PLITHOGENIC LINE GRAPH, STAR GRAPH, AND REGULAR GRAPH,” J. Graph Struct. Appl., 2024. doi: https://doi.org/10.61356/j.plc.2025.4580.
B. S. Panda and S. Verma, “ON PARTIAL GRUNDY COLORING OF BIPARTITE GRAPHS AND CHORDAL GRAPHS,” Discrete Appl. Math., vol. 271, pp. 171–183, 2019. doi: https://doi.org/10.1016/j.dam.2019.08.005.
H. T. Gölpek, “VULNERABILITY OF BANANA TREES VIA CLOSENESS AND RESIDUAL CLOSENESS PARAMETERS,” Maltepe J. Math., vol. 4, no. 2, pp. 33–37, Oct. 2022. doi: https://doi.org/10.47087/mjm.1156370.
A. Ali, H. Iqbal, W. Nazeer, and S. M. Kang, “ON TOPOLOGICAL INDICES FOR THE LINE GRAPH OF FIRECRACKER GRAPH,” Int. J. Pure Appl. Math., vol. 116, no. 4, pp. 1035–1042, 2017. doi: https://zenodo.org/doi/10.5281/zenodo.17785284.
R. Ponraj, A. Gayathri, and S. Somasundaram, “4−Remainder Cordial of Some Tree Related Graphs,” Int. J. Math. Comb., vol. 2, pp. 56–71, 2022. doi: https://zenodo.org/doi/10.5281/zenodo.17785446.
Raventino and S. Yeni, “DIACHROMATIC NUMBER OF SOME ACYCLIC DIGRAPHS,” J. Indones. Math. Soc., vol. 31, no. 3, pp. 1710–1727, 2025. doi: https://doi.org/10.22342/jims.v31i3.1710.
P. Aboulker, É. Bonnet, E. J. Kim, and F. Sikora, “GRUNDY COLORING AND FRIENDS, HALF-GRAPHS, BICLIQUES,” Algorithmica, vol. 85, no. 1, pp. 1–28, 2023. doi: https://doi.org/10.1007/s00453-022-01001-2.
Copyright (c) 2026 Raventino Raventino, Fransiskus Fran
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)
