Exponents of a class of special three-colored primitive digraphs with $ n $ vertices in graph theory

Meijin Luo; Qiutao Qin; Meijin Luo; Qiutao Qin

doi:10.3934/math.2025435

AIMS Mathematics

2025, Volume 10, Issue 4: 9415-9434. doi: 10.3934/math.2025435

Previous Article Next Article

Research article Topical Sections

Exponents of a class of special three-colored primitive digraphs with $ n $ vertices in graph theory

Meijin Luo ,
Qiutao Qin ^,

School of Mathematics and Physics, Hechi University, Yizhou 546300, China

Received: 13 November 2024 Revised: 13 April 2025 Accepted: 18 April 2025 Published: 24 April 2025
MSC : 05C20, 05C50

The exponent problems of the three-colored digraphs containing $ n $ vertices, one $ n $-cycle, one $ (n-3) $-cycle, and one $ 3 $-cycle are considered. According to the coloring of the $ 3 $-cycle, we only consider the case where there are zero red arcs, one yellow arc, and two blue arcs in the 3-cycle. The primitive conditions of the cycle matrix are given, based on the discussion of different cases, the upper bound of the primitive exponents is found, and the extreme digraphs are characterized. The results are useful for the study of the primitive exponents of three-colored digraphs in general cases and the application of graph coloring problems.
- three-colored,
- primitive,
- exponent,
- upper bound,
- extreme digraph
Citation: Meijin Luo, Qiutao Qin. Exponents of a class of special three-colored primitive digraphs with $ n $ vertices in graph theory[J]. AIMS Mathematics, 2025, 10(4): 9415-9434. doi: 10.3934/math.2025435

Related Papers:

Abstract

The exponent problems of the three-colored digraphs containing $ n $ vertices, one $ n $-cycle, one $ (n-3) $-cycle, and one $ 3 $-cycle are considered. According to the coloring of the $ 3 $-cycle, we only consider the case where there are zero red arcs, one yellow arc, and two blue arcs in the 3-cycle. The primitive conditions of the cycle matrix are given, based on the discussion of different cases, the upper bound of the primitive exponents is found, and the extreme digraphs are characterized. The results are useful for the study of the primitive exponents of three-colored digraphs in general cases and the application of graph coloring problems.

References

[1]	D. Bravo, F. Cubría, M. Fiori, V. Trevisan, Characterization of digraphs with three complementarity eigenvalues, J. Algebraic Comb., 57 (2023), 1173–1193. https://doi.org/10.1007/s10801-023-01218-6 doi: 10.1007/s10801-023-01218-6
[2]	J. Méndez, R. Reyes, J. M. Rodríguez, J. M. Sigarreta, Gromov hyperbolicity of Johnson and Kneser graphs, Aequationes Math., 98 (2024), 661–686. https://doi.org/10.1007/s00010-024-01076-y doi: 10.1007/s00010-024-01076-y
[3]	T. H. Han, K. Y. Jang, Y. T. Dong, R. H. Friend, E. H. Sargent, T. W. Lee, A roadmap for the commercialization of perovskite light emitters, Nat. Rev. Mater., 7 (2022), 757–777. https://doi.org/10.1038/s41578-022-00459-4 doi: 10.1038/s41578-022-00459-4
[4]	J. Guo, Y. H. Fu, W. J. Zheng, M. Y. Xie, Y. C. Huang, Z. Y. Miao, et al., Entropy-driven strongly confined low-toxicity pure-red perovskite quantum dots for spectrally stable light-emitting diodes, Nano Lett., 24 (2024), 417–423. https://doi.org/10.1021/acs.nanolett.3c04214 doi: 10.1021/acs.nanolett.3c04214
[5]	Z. F. Wang, S. Z. Ye, H. Wang, Q. J. Huang, J. He, S. Chang, Graph representation-based machine learning framework for predicting electronic band structures of quantum-confined nanostructures, Sci. China Mater., 65 (2022), 3157–3170. https://doi.org/10.1007/s40843-022-2103-9 doi: 10.1007/s40843-022-2103-9
[6]	Y. Tokuhara, T. Akutsu, J. M. Schwartz, J. C. Nacher, A practically efficient algorithm for identifying critical control proteins in directed probabilistic biological networks, npj Syst. Biol. Appl., 10 (2024), 87. https://doi.org/10.1038/s41540-024-00411-y doi: 10.1038/s41540-024-00411-y
[7]	A. Rahimi, A. Mirzazadeh, S. Tavakolpour, Genetics and genomics of SARS-CoV-2: a review of the literature with the special focus on genetic diversity and SARS-CoV-2 genome detection, Genomics, 113 (2021), 1221–1232. https://doi.org/10.1016/j.ygeno.2020.09.059 doi: 10.1016/j.ygeno.2020.09.059
[8]	Y. L. Wang, Y. F. Sun, Z. L. Shen, C. Wang, J. Qian, Q. Y. Mao, et al., Fully human single-domain antibody targeting a highly conserved cryptic epitope on the Nipah virus G protein, Nat. Commun., 15 (2024), 6892. https://doi.org/10.1038/s41467-024-51066-6 doi: 10.1038/s41467-024-51066-6
[9]	Y. M. Si, D. H. Zhou, J. Zhao, Y. F. Peng, P. Z. Chen, J. L. Fan, et al., Radiation chemistry of a novel zinc-oxo cluster crosslinking strategy for EUV patterning, Sci. China Mater., 67 (2024), 1588–1593. https://doi.org/10.1007/s40843-023-2827-8 doi: 10.1007/s40843-023-2827-8
[10]	Y. J. Wang, Research on graph invariants as well as their applications in complex networks, North University of China, 2021.
[11]	H. P. Sun, A study of heuristic algorithms for graph coloring problem, Guangzhou University, 2023.
[12]	J. H. Song, X. F. Wang, S. M. Hu, J. W. Jia, D. Yan, Algorithmic research overview on graph coloring problems, Comput. Eng. Appl., 60 (2024), 66–77. https://doi.org/10.3778/j.issn.1002-8331.2403-0434 doi: 10.3778/j.issn.1002-8331.2403-0434
[13]	R. A. Brualdi, H. J. Ryser, Combinatorial matrix theory, Cambridge University Press, 1991. https://doi.org/10.1017/cbo9781107325708
[14]	B. L. Shader, S. Suwilo, Exponents of nonnegative matrix pairs, Linear Algebra Appl., 363 (2003), 275–293. https://doi.org/10.1016/s0024-3795(01)00566-3 doi: 10.1016/s0024-3795(01)00566-3
[15]	Y. B. Gao, Y. L. Shao, Exponents of two-colored digraphs with two cycles, Linear Algebra Appl., 407 (2005), 263–276. https://doi.org/10.1016/j.laa.2005.05.004 doi: 10.1016/j.laa.2005.05.004
[16]	X. Li, Primitive exponents of a class of special two-colored digraphs, J. Jiangsu Normal Univ., 30 (2012), 6–8.
[17]	J. Q. Lin, Exponents of a class of two-colored digraphs with directed and double directed cycles alternated, J. Taiyuan Normal Univ., 11 (2012), 16–19.
[18]	Mulyono, H. Sumardi, S. Suwilo, The scrambling index of primitive two-colored two cycles whose lengths differ by 1, Far East J. Math. Sci., 96 (2015), 113–132. https://doi.org/10.17654/FJMSJan2015_113_132 doi: 10.17654/FJMSJan2015_113_132
[19]	M. J. Luo, X. Li, S. Tao, Upper bound of primitive exponent of a class of nonnegative matrix pairs, Proceedings of the 4th International Conference on Information Technology and Management Innovation, 2015, 34–37. https://doi.org/10.2991/icitmi-15.2015.7
[20]	P. Yang, Y. B. Gao, Primitive exponents of a class of two-colored digraphs with two cycles, J. North Univ. China, 30 (2009), 405–409.
[21]	Y. Ma, S. X. Chen, The base set of primitive non-powerful signed simple graphs, Math. Theory Appl., 34 (2014), 61–65.
[22]	M. J. Luo, X. D. Li, Z. Y. Hou, X. Li, Exponents of a class of special primitive three-colored digraphs with three cycles, Ars Comb., 148 (2020), 33–46.
[23]	Q. Yan, Y. L. Shao, Exponents of a class of three-colored digraphs, J. North Univ. China, 30 (2009), 512–517.
[24]	H. Q. Liu, Primitive exponents of a class of three-colored digraphs with two $m$-cycles, Shanxi Agric. Univ., 30 (2010), 380–384. https://doi.org/10.13842/j.cnki.issn1671-8151.2010.04.007 doi: 10.13842/j.cnki.issn1671-8151.2010.04.007
[25]	H. L. Zhou, Q. Y. Song, Exponents of a class of three-colored digraphs, J. Jilin Normal Univ., 5 (2011), 82–89. https://doi.org/10.16862/j.cnki.issn1674-3873.2011.02.022 doi: 10.16862/j.cnki.issn1674-3873.2011.02.022

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)