Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On existence of Two Classes of Generalized Howell Designs with Block Size Three and Index Two

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Let \(t, k, {\lambda }, s\) and v be nonnegative integers, and let X be a set of v symbols. A generalized Howell design, denoted t-GHD\(_k (s, v; {\lambda })\), is an \(s \times s\) array, each cell of which is either empty or contains a k-set of symbols from X, called a block, such that: (i) each symbol appears exactly once in each row and in each column (i.e. each row and column is a resolution of X); (ii) no t-subset of elements from X appears in more than \({\lambda }\) cells. A generalized Howell design is a class of doubly resolvable designs , which generalize a number of well-known objects. Particular instances of the parameters correspond to generalized Howell designs are doubly resolvable group divisible designs (DRGDDs). In this paper, we concentrate on the case that \(t=2,k=3\) and \({\lambda }= 2\), and simply write GHD(s, v; 2). The spectrum of GHD\((3n-3,3n;2)\)’s and GHD\((6n-6,6n;2)\)’s is completely established by solving the existence of (3, 2)-DRGDDs of types \(3^n\) and \(6^n\). At the same time, we also survey rummage the existence of GHD\(_4(n,4n;1)\)’s. As their applications, several new classes of multiply constant-weight codes are obtained.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abel, R.J.R.: Existence of five MOLS of orders 18 and 60. J. Combust. Des. 23, 135–139 (2015)

    MathSciNet  MATH  Google Scholar 

  2. Abel, R.J.R., Bailey, R.F., Burgess, A.C., Danziger, P., Mendelsohn, E.: On generalized Howell designs with block size three. Des. Codes Cryptogr. 81, 365–391 (2016)

    Article  MathSciNet  Google Scholar 

  3. Abel, R.J.R., Bennett, F.E., Greig, M.: PBD-closure. In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, 2nd edn, pp. 247–255. CRC Press, Boca Raton (2007)

    Google Scholar 

  4. Abel, R.J.R., Chan, N., Colbourn, C.J., Lamken, E.R., Wang, C., Wang, J.: Doubly resolvable nearly Kirkman triple systems. J. Combin. Des. 21, 342–358 (2013)

    Article  MathSciNet  Google Scholar 

  5. Abel, R.J.R., Lamken, E.R., Wang, J.: A few more Kirkman squares and doubly near resolvable BIBDs with block size \(3\). Discrete Math. 308, 1102–1123 (2008)

    Article  MathSciNet  Google Scholar 

  6. Anderson, B.A., Schellenberg, P.J., Stinson, D.R.: The existence of Howell designs of even side. J. Comb. Theory Ser. A 36, 23–55 (1984)

    Article  MathSciNet  Google Scholar 

  7. Arhin, J.: On the construction and structure of SOMAs and related partial linear spaces. Ph.D. Thesis, University of London (2006)

  8. Arhin, J.: Every SOMA\((n-2, n)\) is Trojan. Discret. Math. 310, 303–311 (2010)

    Article  MathSciNet  Google Scholar 

  9. Brickell, E.F.: A few results in message authentication. Congr. Numer. 43, 141–154 (1984)

    MathSciNet  MATH  Google Scholar 

  10. Chee, Y.M., Cherif, Z., Danger, J.L., Guilley, S., Kiah, H.M., Kim, J.L., Solé, P., Zhang, X.: Multiply constant-weight codes and the reliability of loop physically unclonable functions. IEEE Trans. Inf. Theory 60, 7026–7034 (2014)

    Article  MathSciNet  Google Scholar 

  11. Chee, Y.M., Kiah, H.M., Purkayastha, P.: Matrix codes and multitone frequency shift keying for power line communications. In: Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, July 2013, pp. 2870-2874

  12. Chee, Y.M., Kiah, H.M., Zhang, H., Zhang, X.: Constructions of optimal and near-optimal multiply constant-weight codes. IEEE Trans. Inf. Theory 63, 3621–3629 (2017)

    Article  MathSciNet  Google Scholar 

  13. Cherif, Z., Danger, J.L., Guilley, S., Bossuet, L.: An easy-to-design puf based on a single oscillator: the loop puf. In: Proceedings of the 2012 15th Euromicro Conference on Digital System Design, ser. DSD12, 2012, pp. 156-162

  14. Cherif, Z., Danger, J.L., Guilley, S., Kim, J.L., Solé, P.: Multiply constant weight codes. In: Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, July 2013

  15. Colbourn, C.J., Curran, D., Vanstone, S.A.: Recursive constructions for Kirkman squares with block size 3. Util. Math. 32, 169–174 (1987)

    MathSciNet  MATH  Google Scholar 

  16. Colbourn, C.J., Dinitz, J.H. (eds.): The CRC Handbook of Combinatorial Designs, 2nd edn. CRC Press, Boca Raton (2007)

    MATH  Google Scholar 

  17. Colbourn, C.J., Lamken, E.R., Ling, A.C.H., Mills, W.H.: The existence of Kirkman squares-doubly resolvable \((v, 3, 1)\)-BIBDs. Des. Codes Cryptogr. 26, 169–196 (2002)

    Article  MathSciNet  Google Scholar 

  18. Colbourn, C.J., Manson, K.E., Wallis, W.D.: Frames for twofold triple systems. Ars Combin. 17, 65–74 (1984)

    MathSciNet  MATH  Google Scholar 

  19. Colbourn, C.J.: Doubly resolvable twofold triple systems, ProcEleventh Manitoba Conf. Numer. Math. Computing. Congr. Numer. 34, 219–223 (1982)

    Google Scholar 

  20. Deza, M., Vanstone, S.A.: Bounds for permutation arrays. J. Stat. Plan. Inference 2, 197–209 (1978)

    Article  MathSciNet  Google Scholar 

  21. Dinitz, J.H., Stinson, D.R.: Room squares and related designs. In: Dinitz, J.H., Stinson, D.R. (eds.) Contemporary Design Theory: A Collection of Surveys, pp. 137–204. Wiley, New York (1992)

    MATH  Google Scholar 

  22. Du, J., Abel, R.J.R., Wang, J.: Some new resolvable GDDs with \(k=4\) and doubly resolvable GDDs with \(k=3\). Discrete Math. 338, 2015–2118 (2015)

    Article  MathSciNet  Google Scholar 

  23. Etzion, T.: Optimal doubly constant weight codes. J. Comb. Des. 16, 137–151 (2008)

    Article  MathSciNet  Google Scholar 

  24. Fuji-Hara, R., Vanstone, S.A.: The existence of orthogonal resolutions of lines in \(AG(n, q)\). J. Comb. Theory Ser. A 45, 139–147 (1987)

    Article  MathSciNet  Google Scholar 

  25. Lamken, E.R.: \(3\)-complementary frames and doubly near resolvable \((v,3,2)\)-BIBDs. Discrete Math. 88, 59–78 (1991)

    Article  MathSciNet  Google Scholar 

  26. Lamken, E.R.: The existence of doubly resolvable \((v,3,2)\)-BIBDs. J. Combin. Theory Ser. A 72, 50–76 (1995)

    Article  MathSciNet  Google Scholar 

  27. Lamken, E.R.: Designs with mutually orthogonal resolutions and decompositions of edge-colored complete graphs. J. Comb. Des. 17, 425–447 (2009)

    Article  Google Scholar 

  28. Mullin, R.C., Wallis, W.D.: The existence of Room squares. Aequ. Math. 1, 1–7 (1975)

    Article  MathSciNet  Google Scholar 

  29. Ordentlich, E., Roth, R.: Two-dimensional weight-constrained codes through enumeration bounds. IEEE Trans. Inf. Theory 46, 1292–1301 (2000)

    Article  MathSciNet  Google Scholar 

  30. Ordentlich, E., Roth, R.: Low complexity two-dimensional weight-constrained codes. IEEE Trans. Inf. Theory 58, 3892–3899 (2012)

    Article  MathSciNet  Google Scholar 

  31. Phillips, N.C.K., Wallis, W.D.: All solutions to a tournament problem. Congr. Numer. 114, 193–196 (1996)

    MathSciNet  MATH  Google Scholar 

  32. Rosa, A., Vanstone, S.A.: Starter-adder techniques for Kirkman squares and Kirkman cubes of small sides. Ars Comb. 14, 199–212 (1982)

    MathSciNet  MATH  Google Scholar 

  33. Soicher, L.H.: On the structure and classification of SOMAs: generalizations of mutually orthogonal Latin squares. Electron. J. Comb. 6(1), R32 (1999)

    Article  MathSciNet  Google Scholar 

  34. Soicher, L.H.: SOMA Update http://www.maths.qmul.ac.uk/~leonard/soma/. Accessed 27 July 2012

  35. Stinson, D.R.: The existence of Howell designs of odd side. J. Comb. Theory Ser. A 32, 53–65 (1982)

    Article  MathSciNet  Google Scholar 

  36. Todorov, D.T.: Four mutually orthogonal Latin squares of order 14. J. Comb. Des. 20, 363–367 (2012)

    Article  MathSciNet  Google Scholar 

  37. Vanstone, S.A.: On mutually orthogonal resolutions and near resolutions. Ann. Discrete Math. 15, 357–369 (1982)

    MathSciNet  MATH  Google Scholar 

  38. Wang, C., Chang, Y., Feng, T.: Optimal multiply constant-weight codes from generalized Howell designs. Graphs Combin. 35, 611–632 (2019)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the referees for their careful reading of the original version of this paper, their detailed comments and the suggestions that much improved the quality of this paper.

Author information

Authors and Affiliations

  1. School of Sciences, Nantong University, Nantong, 226007, People’s Republic of China

    Jing Shi & Jinhua Wang

Authors
  1. Jing Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinhua Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jinhua Wang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Research supported by the National Natural Science Foundation of China under Grant No. 11371207.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (PDF 149 kb)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shi, J., Wang, J. On existence of Two Classes of Generalized Howell Designs with Block Size Three and Index Two. Graphs and Combinatorics 36, 1525–1543 (2020). https://doi.org/10.1007/s00373-020-02198-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-020-02198-1

Keywords

Mathematics Subject Classification

Search

Navigation