Mixed-level detecting arrays on graphs

Quanrui Zhang; Ce Shi; Yonggang Yi; Quanrui Zhang; Ce Shi; Yonggang Yi

doi:10.3934/era.2025292

Electronic Research Archive

2025, Volume 33, Issue 11: 6610-6630. doi: 10.3934/era.2025292

Previous Article Next Article

Research article

Mixed-level detecting arrays on graphs

1.
School of Information Science and Technology, Yunnan Normal University, Kunming 650500, China
2.
School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Finance, Shanghai 201209, China
3.
Shanghai Normal University Tianhua College, Shanghai 201815, China

Received: 22 August 2025 Revised: 18 October 2025 Accepted: 24 October 2025 Published: 11 November 2025

The purpose of this paper was to develop a unified combinatorial framework for fault localization in heterogeneous software systems, where parameters may have different numbers of levels. Specifically, we investigated mixed-level detecting arrays (MDAs) on graphs, extending the classical detecting array model to accommodate non-uniform factor structures. In this paper, we established an optimality criterion that minimizes the number of required test cases and analyzes the structural and combinatorial properties of optimal MDAs on graphs. Furthermore, several constructive methods were proposed to generate optimal arrays, and existence results were derived that achieve the theoretical lower bounds. The findings enhance the theoretical understanding of detecting arrays in graph-based settings and provide practical guidelines for designing cost-efficient and fault-sensitive test suites in complex, heterogeneous software systems.
- combinatorial testing,
- detecting arrays,
- mixed-level factors,
- graph-based testing,
- optimality criterion
Citation: Quanrui Zhang, Ce Shi, Yonggang Yi. Mixed-level detecting arrays on graphs[J]. Electronic Research Archive, 2025, 33(11): 6610-6630. doi: 10.3934/era.2025292

Related Papers:

Abstract

The purpose of this paper was to develop a unified combinatorial framework for fault localization in heterogeneous software systems, where parameters may have different numbers of levels. Specifically, we investigated mixed-level detecting arrays (MDAs) on graphs, extending the classical detecting array model to accommodate non-uniform factor structures. In this paper, we established an optimality criterion that minimizes the number of required test cases and analyzes the structural and combinatorial properties of optimal MDAs on graphs. Furthermore, several constructive methods were proposed to generate optimal arrays, and existence results were derived that achieve the theoretical lower bounds. The findings enhance the theoretical understanding of detecting arrays in graph-based settings and provide practical guidelines for designing cost-efficient and fault-sensitive test suites in complex, heterogeneous software systems.

References

[1]	D. R. Kuhn, R. N. Kacker, Y. Lei, Introduction to Combinatorial Testing, Chapman and Hall/CRC, Boca Raton, FL, USA, 2013.
[2]	C. Nie, H. Leung, A survey of combinatorial testing, ACM Comput. Surv., 43 (2011), 1–29. https://doi.org/10.1145/1883612.1883618 doi: 10.1145/1883612.1883618
[3]	C. J. Colbourn, Strength two covering arrays: Existence tables and projection, Discrete Math., 308 (2008), 772–786. https://doi.org/10.1016/j.disc.2007.07.050 doi: 10.1016/j.disc.2007.07.050
[4]	J. T. Jimenez, I. I. Marquez, Covering arrays of strength three from extended permutation vectors, Des. Codes Cryptogr., 86 (2018), 2629–2643. https://doi.org/10.1007/s10623-018-0465-6 doi: 10.1007/s10623-018-0465-6
[5]	J. T. Jimenez, I. I. Marquez, Improved covering arrays using covering perfect hash families with groups of restricted entries, Appl. Math. Comput., 369 (2020), 124826. https://doi.org/10.1016/j.amc.2019.124826 doi: 10.1016/j.amc.2019.124826
[6]	L. Ji, J. Yin, Constructions of new orthogonal arrays and covering arrays of strength three, J. Comb. Theory Ser. A, 117 (2010), 236–247. https://doi.org/10.1016/j.jcta.2009.06.002 doi: 10.1016/j.jcta.2009.06.002
[7]	L. G. Hernandez, New bounds for mixed covering arrays in $t$-way testing with uniform strength, Inf. Softw. Technol., 59 (2024), 17–32. https://doi.org/10.1016/j.infsof.2014.10.009 doi: 10.1016/j.infsof.2014.10.009
[8]	I. I. Marquez, J. T. Jimenez, B. A. Ju$\acute{a}$rez, H. A. George, A greedy-metaheuristic 3-stage approach to construct covering arrays, Inf. Sci., 460-461 (2018), 172–189. https://doi.org/10.1016/j.ins.2018.05.047 doi: 10.1016/j.ins.2018.05.047
[9]	K. Sarkar, C. J. Colbourn, Two-stage algorithms for covering array construction, J. Comb. Des., 27 (2019), 475–505. https://doi.org/10.1002/jcd.21657 doi: 10.1002/jcd.21657
[10]	K. Shokri, L. Moura, New families of strength $3$ covering arrays using linear feedback shift register sequences, J. Comb. Des., 33 (2025), 156–171. https://doi.org/10.1002/jcd.21963 doi: 10.1002/jcd.21963
[11]	S. Raaphorst, L. Moura, B. Stevens, A construction for strength-3 covering arrays from linear feedback shift register sequences, Des. Codes Cryptogr., 73 (2014), 949–968. https://doi.org/10.1007/s10623-013-9835-2 doi: 10.1007/s10623-013-9835-2
[12]	G. Tzanakis, L. Moura, D. Panario, B. Stevens, Covering arrays from $m$-sequences and character sums, Des. Codes Cryptogr., 85 (2017), 437–456. https://doi.org/10.1007/s10623-016-0316-2 doi: 10.1007/s10623-016-0316-2
[13]	C. J. Colbourn, C. Shi, C. M. Wang, J. Yan, Mixed covering arrays of strength three with few factors, J. Stat. Plann. Inference, 141 (2011), 3640–3647. https://doi.org/10.1016/j.jspi.2011.05.018 doi: 10.1016/j.jspi.2011.05.018
[14]	L. Moura, J. Stardom, B. Stevens, A. Williams, Covering arrays with mixed alphabet sizes, J. Combin. Des., 11 (2003), 413–432. https://doi.org/10.1002/jcd.10059 doi: 10.1002/jcd.10059
[15]	K. Meagher, B. Stevens, Covering arrays on graphs, J. Comb. Theory Ser. B, 95 (2005), 134–151. https://doi.org/10.1016/j.jctb.2005.03.005
[16]	K. Meagher, L. Moura, L. Zekaoui, Mixed covering arrays on graphs, J. Comb. Des., 15 (2007), 393–404. https://doi.org/10.1002/jcd.20149 doi: 10.1002/jcd.20149
[17]	P. Danziger, E. Mendelsohn, L. Moura, B. Stevens, Covering arrays avoiding forbidden edges, Theor. Comput. Sci., 410 (2009), 5403–5414. https://doi.org/10.1016/j.tcs.2009.07.057 doi: 10.1016/j.tcs.2009.07.057
[18]	C. J. Colbourn, D. W. McClary, Locating and detecting arrays for interaction faults, J. Comb. Optim., 15 (2008), 17–48. https://doi.org/10.1007/s10878-007-9082-4 doi: 10.1007/s10878-007-9082-4
[19]	C. M. Wang, C. Shi, T. Tsuchiya, Q. R. Zhang, Detecting arrays on graphs, Electron. Res. Arch., 33 (2025), 3328–3347. https://doi.org/10.3934/era.2025147
[20]	C. Shi, L. Jiang, A. Y. Tao, Consecutive detecting arrays for interaction faults, Graphs Combin., 36 (2020), 1203–1218. https://doi.org/10.1007/s00373-020-02176-7 doi: 10.1007/s00373-020-02176-7
[21]	C. Shi, A. Tao, Consecutive detecting arrays from $m$-sequence, IAENG Int. J. Appl. Math., 50 (2020), 80–86.
[22]	Y. Tang, J. X. Yin, Detecting arrays and their optimality, Acta Math. Sin. Engl. Ser., 27 (2011), 2309–2318. https://doi.org/10.1007/s10114-011-0184-7 doi: 10.1007/s10114-011-0184-7
[23]	C. Shi, Y. Tang, J. X. Yin, The equivalence between optimal detecting arrays and super-simple OAs, Des. Codes Cryptogr., 62 (2012), 131–142. https://doi.org/10.1007/s10623-011-9498-9 doi: 10.1007/s10623-011-9498-9
[24]	C. Shi, Y. Tang, J. X. Yin, Optimum mixed level detecting arrays, Ann. Stat., 42 (2014), 1546–1563. https://doi.org/10.1214/14-AOS1228 doi: 10.1214/14-AOS1228
[25]	C. Shi, Optimum Super-simple mixed covering arrays of type $a^1b^{k-1}$, Acta Math. Sin. Engl. Ser., 33 (2017), 153–164. https://doi.org/10.1002/jcd.21657 doi: 10.1002/jcd.21657
[26]	J. B. Liu, X. Wang, L. Hua, J. D. Cao, L. P. Chen, The coherence and robustness analysis for a family of unbalanced networks, IEEE Trans. Signal Inf. Process. Netw., 11 (2025), 378–387. https://doi.org/10.1109/tsipn.2025.3555164 doi: 10.1109/tsipn.2025.3555164
[27]	J. B. Liu, L. Guan, J. D. Cao, Property analysis and coherence dynamics for tree-symmetric networks with noise disturbance, J. Complex Netw., 12 (2024), 475–505. https://doi.org/10.1093/comnet/cnae029 doi: 10.1093/comnet/cnae029
[28]	R. El-Shanawany, A. El-Mesady, S. M. Shaaban, Mutually orthogonal graph squares for disjoint union of paths, Appl. Math. Sci., 12 (2018), 303–310. https://doi.org/10.1155/2022/9308708 doi: 10.1155/2022/9308708

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)