Detecting arrays on graphs

Chengmin Wang; Ce Shi; Tatsuhiro Tsuchiya; Quanrui Zhang; Chengmin Wang; Ce Shi; Tatsuhiro Tsuchiya; Quanrui Zhang

doi:10.3934/era.2025147

Electronic Research Archive

2025, Volume 33, Issue 5: 3328-3347. doi: 10.3934/era.2025147

Previous Article Next Article

Research article

Detecting arrays on graphs

1.
Department of Mathematics, Taizhou University, Taizhou 225300, China
2.
School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Finance, Shanghai 201209, China
3.
Graduate School of Information Science and Technology, Osaka University, Suita 565-0871, Japan
4.
School of Information Science and Technology, Yunnan Normal University, Kunming 650500, China

Received: 31 December 2024 Revised: 13 May 2025 Accepted: 23 May 2025 Published: 28 May 2025

Covering arrays on graphs can be used to generate test suites in component-based systems but they cannot identify and determine faulty interactions from the outcome of the test. To address this problem, the notion of detecting arrays on graphs (DAGs) was proposed in this paper. Then, the equivalence and the existence of DAGs were intensively studied. We established a general criterion for measuring the optimality of DAGs in terms of their size. Based on this optimality criterion, the equivalence between optimal DAGs and orthogonal arrays with prescribed properties was established. With this equivalence property, a great number of optimal detecting arrays on cycles were produced by constructing the equivalent combinatorial configurations. In particular, the existence of optimal detecting arrays on cycles with few vertices was almost completely determined.
- combinatorial testing,
- interaction faults,
- detecting arrays on graphs,
- orthogonal arrays on graphs,
- optimality,
- $ M $-sequence
Citation: Chengmin Wang, Ce Shi, Tatsuhiro Tsuchiya, Quanrui Zhang. Detecting arrays on graphs[J]. Electronic Research Archive, 2025, 33(5): 3328-3347. doi: 10.3934/era.2025147

Related Papers:

Abstract

Covering arrays on graphs can be used to generate test suites in component-based systems but they cannot identify and determine faulty interactions from the outcome of the test. To address this problem, the notion of detecting arrays on graphs (DAGs) was proposed in this paper. Then, the equivalence and the existence of DAGs were intensively studied. We established a general criterion for measuring the optimality of DAGs in terms of their size. Based on this optimality criterion, the equivalence between optimal DAGs and orthogonal arrays with prescribed properties was established. With this equivalence property, a great number of optimal detecting arrays on cycles were produced by constructing the equivalent combinatorial configurations. In particular, the existence of optimal detecting arrays on cycles with few vertices was almost completely determined.

References

[1]	C. J. Colbourn, CRC Handbook of Combinatorial Designs, CRC Press, 2010. https://doi.org/10.1201/9781003040897
[2]	D. R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer, New York, 2004. https://doi.org/10.1007/b97564
[3]	D. R. Kuhn, R. N. Kacker, Y. Lei, Introduction to Combinatorial Testing, CRC Press, 2013. https://dl.acm.org/doi/book/10.5555/2500930
[4]	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
[5]	C. J. Colbourn, S. S. Martirosyan, T. V. Trung, R. A. Walker, Roux-type constructions for covering arrays of strengths three and four, Des. Codes Cryptogr., 41 (2006), 33–57. https://doi.org/10.1007/s10623-006-0020-8 doi: 10.1007/s10623-006-0020-8
[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]	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
[8]	A. Hartman, L. Raskin, Problems and algorithms for covering arrays, Discrete Math., 284 (2004), 149–156. https://doi.org/10.1016/j.disc.2003.11.029 doi: 10.1016/j.disc.2003.11.029
[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]	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
[11]	Covering array tables for $t = 2, 3, 4, 5, 6$, 2020. Available from: https://www.public.asu.edu/ccolbou/src/tabby/2-3-ca.html
[12]	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 doi: 10.1016/j.jctb.2005.03.005
[13]	A. El-Mesady, O. Bazighifan, H. M. Shabana, On graph transversal designs and graph-authentication codes based on mutually orthogonal graph squares, J. Math., (2022), 8992934. https://doi.org/10.1155/2022/8992934 doi: 10.1155/2022/8992934
[14]	M. Higazy, A. El-Mesady, M. S. Mohamed, On graph-orthogonal arrays by mutually orthogonal graph squares, Symmetry, 12 (2020), 1895. https://doi.org/10.3390/sym12111895 doi: 10.3390/sym12111895
[15]	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
[16]	T. Mahapatra, M. Pal, An investigation on m-polar fuzzy threshold graph and its application on resource power controlling system, J. Ambient Intell. Humaniz. Comput., 13 (2022), 501–514. https://doi.org/10.1007/s12652-021-02914-6 doi: 10.1007/s12652-021-02914-6
[17]	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
[18]	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
[19]	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
[20]	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
[21]	C. Shi, B. Wen, J. Lin, Cyclic consecutive orthogonal arrays, Acta Math. Appl. Sin., 39 (2016), 786–800.
[22]	C. R. Rao, Factorial experiments derivable from combinatorial arrangements of arrays, Suppl. J. Roy. Stat. Soc., 9 (1947), 128–139. https://doi.org/10.2307/2983576 doi: 10.2307/2983576
[23]	A. S. Hedayat, N. J. A. Sloane, J. Stufken, Orthogonal Arrays: Theory and Applications, Springer-Verlag, New York, 1999. http://dx.doi.org/10.1007/978-1-4612-1478-6
[24]	K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Stat., 23 (1952), 426–434. https://doi.org/10.1214/aoms/1177729387 doi: 10.1214/aoms/1177729387
[25]	S. W. Golomb, G. Gong, Signal Design for Good Correlation for Wireless Communication, Cryptography, Radar, Cambridge Univ. Press, Cambridge, UK, 2005. https://doi.org/10.1017/CBO9780511546907
[26]	A. G. Castoldi, L. Moura, D. Panario, B. Stevens, Ordered orthogonal array construction using LFSR sequences, IEEE Trans. Inf. Theory, 63 (2017), 1336–1346. https://doi.org/10.1109/tit.2016.2634010 doi: 10.1109/tit.2016.2634010
[27]	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
[28]	C. Shi, A. Tao, Consecutive detecting arrays from $m$-sequence, IAENG Int. J. Appl. Math., 50 (2020), 80–86.
[29]	S. Hartman, On simple and supersimple transversal designs, J. Comb. Des., 8 (2000), 311–322. https://doi.org/10.1002/1520-6610(2000)8:5%3C311::AID-JCD1%3E3.0.CO; 2-1 doi: 10.1002/1520-6610(2000)8:5%3C311::AID-JCD1%3E3.0.CO;2-1
[30]	Y. H. Chen, Constructions of Optimal Detecting Arrays of Degree $5$ and Strength $2$, Master thesis, Soochow University in Suzhou, 2011.
[31]	J. B. Liu, C. Wang, S. Wang, B. Wei, Zagreb indices and multiplicative zagreb indices of eulerian graphs, Bull. Malays. Math. Sci. Soc., 42 (2019), 67–78. https://doi.org/10.1007/s40840-017-0463-2 doi: 10.1007/s40840-017-0463-2
[32]	J. B. Liu, L. Guan, J. Cao, L. Chen, Coherence analysis for a class of polygon networks with the noise disturbance, IEEE Trans. Syst. Man Cyber. Syst., 2025 (2025). https://doi.org/10.1109/TSMC.2025.3559326 doi: 10.1109/TSMC.2025.3559326
[33]	Y. Akhtar, S. Maity, Covering arrays on product graphs, Graphs Combin., 33 (2017), 635–652. https://doi.org/10.1007/s00373-017-1800-9 doi: 10.1007/s00373-017-1800-9
[34]	A. El-Mesady, Y. S. Hamed, K. M. Abualnaja, A novel application on mutually orthogonal graph squares and graph-orthogonal arrays, Mathematics, 7 (2022), 7349C7373. https://doi.org/10.3934/math.2022410 doi: 10.3934/math.2022410
[35]	C. Shi, Y. Tang, J. X. Yin, Optimum mixed level detecting arrays, Ann. Statist., 42 (2014), 1546–1563. https://doi.org/10.1214/14-AOS1228 doi: 10.1214/14-AOS1228
[36]	C. Shi, J. Yin, Existence of super-simple OA$_\lambda(3, 5, v)'$s, Des. Codes Cryptogr., 72 (2014), 369–380. https://doi.org/10.1007/s10623-012-9771-6 doi: 10.1007/s10623-012-9771-6

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)