Detecting arrays on graphs

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

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.

Keywords

combinatorial testing / interaction faults / detecting arrays on graphs / orthogonal arrays on graphs / optimality / M-sequence

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[36] C. Shi, J. Yin, Existence of super-simple OA_λ(3, 5, v)′s , Des. Codes Cryptogr., 72 (2014), 369-380. https://doi.org/10.1007/s10623-012-9771-6