×

Partially balanced incomplete block (PBIB)-designs arising from diametral paths in some strongly regular graphs. (English) Zbl 1523.05001

Summary: The partially balanced incomplete block (PBIB)-designs and association schemes arising from different graph parameters is a well-studied concept. In this paper, we define and construct PBIB-designs with association schemes in strongly regular graphs through the nodes belonging to the diametral paths as blocks. A \((v,b,r,k,\lambda,\mu)\)-design, called a diametral-design (in short) over a strongly regular graph \(G=(V,E)\) of degree \(d\), diameter \(\mathrm{diam}(G)\), is an ordered pair \(D=(V,B)\), where \(V=V(G)\) and \(B\) is the set of all diametral paths of \(G\), called blocks, containing the nodes belonging to the diametral paths, satisfying the following conditions: (i) If \(x\), \(y\in V\) and \(\{x,y\}\in E\), then there are exactly \(\lambda\) blocks containing \(\{x,y\}\); (ii) If \(x\), \(y\in V\), \(x\neq y\) and \(\{x,y\}\notin E \), then there are exactly \(\mu\)-blocks containing \(\{x,y\}\). We construct PBIB-designs with two-association schemes through diametral paths corresponding to the strongly regular graphs such as the square lattice graphs \(L_2(n)\), the triangular graphs \(T(n)\), the three Chang graphs, the Petersen graph, the Shrikhande graph, the Clebsch graph, the complement of Clebsch graph, the complement of Schläfli graph, complete bipartite graphs, the Hoffman-Singleton graph, etc. and in each case we give the composition of the diametral paths. These serve as extensions for the collection of near impossible class of strongly regular graphs with given parameters having two-association schemes.

MSC:

05B05 Combinatorial aspects of block designs
05E30 Association schemes, strongly regular graphs
Full Text: DOI

References:

[1] Berge, C., Theory of Graphs and its Applications (Wiley, New York, 1962). · Zbl 0097.38903
[2] Bose, R. C., Strongly regular graphs, partial geometries and partially balance designs, Pacific J. Math.13 (1963) 389-419. · Zbl 0118.33903
[3] Bose, R. C. and Nair, K. R., Partially balanced incomplete block designs, Sankhya4 (1939) 337-372.
[4] Bose, R. C. and Shimamoto, T., Classification and analysis of partially balanced incomplete block designs with two associate classes, J. Amer. Statist. Assoc.47 (1952) 151-184. · Zbl 0048.11603
[5] Buckley, F. and Harary, F., Distance in Graphs (Addison-Wesley, 1990). · Zbl 0688.05017
[6] Chang, L. C., The uniqueness and non-uniqueness of the triangular association scheme, Sci. Record Peking Math. (New Ser.)3 (1959) 604-614. · Zbl 0089.15102
[7] Clatworthy, W. H., Partially balanced incomplete block designs with two associate classes and two treatments per block, J. Res. Natl. Bur. Stand.54 (1955) 219-227. · Zbl 0068.13403
[8] Colbourn, C. J. and Dinitz, J. H., Handbook of Combinatorial Designs, 2nd edn. (CRC Press, Boca Raton, 2007). · Zbl 1101.05001
[9] Colbourn, C. J. and Van Oorschot, P. C., Applications of combinatorial design in computer science, ACM Comput. Surv.21 (1989) 223-250.
[10] Godsil, C. and Royle, G., Algebraic Graph Theory (Springer-Verlag, New York, 2001). · Zbl 0968.05002
[11] Haemers, W. H., A new partial geometry constructed from the Hoffman-Singleton graph, in Finite Geometries and Designs, eds. Cameron, P. J., Hirschfeld, J. W. P. and Hughes, D. R. (Cambridge University Press, Cambridge, 1981), pp. 119-127. · Zbl 0463.05025
[12] Ionin, Y. J. and Shrikhande, M. S., On classification of two-class partially balanced designs, J. Statist. Plann. Inference95 (2001) 209-228. · Zbl 0985.05004
[13] Lindner, C. C. and Rodger, C. A., Design Theory, 2nd edn. (CRC Press, Boca Raton, 2009). · Zbl 1157.68403
[14] Paola, J. W., Block designs and graph theory, J. Combin. Theory1 (1966) 132-148. · Zbl 0168.01703
[15] Raghavarao, D., Construction and Combinatorial Problems in Design of Experiments (John Wiley, New York, 1971). · Zbl 0222.62036
[16] Walikar, H. B., Acharya, B. D. and Shirkol, S., Designs associated with maximum independent sets of graph, Des. Codes Cryptogr.57 (2010) 91-105. · Zbl 1230.05084
[17] E. W. Weisstein, Generalized Quadrangle, from MathWorld-A Wolfram Web Resource, http://mathworld.wolfram.com/Generalized Quadrangle.html.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.