Bipartite graphs with five eigenvalues and pseudo designs
Ebrahim Ghorbani
Department of Mathematics, K.N. Toosi University of Technology, P.O. Box 16315-1618, Tehran, Iran
DOI: 10.1007/s10801-011-0331-3
Abstract
A pseudo (v,k,λ)-design is a pair $(X, \mathcal{B})$ , where X is a v-set, and $\mathcal{B}=\{B_{1},\ldots,B_{v-1}\}$ is a collection of k-subsets (blocks) of X such that any two distinct B i ,B j intersect in λ elements, and 0\leq λ<k\leq v - 1. We use the notion of pseudo designs to characterize graphs of order n whose (adjacency) spectrum contains zero and \pm θ with multiplicity (n - 3)/2 where $0<θ\le\sqrt{2}$ . Meanwhile, partial results confirming a conjecture of O. Marrero on a characterization of pseudo (v,k,λ)-designs are obtained.
Pages: 209–221
Keywords: spectrum of graph; pseudo design; BIBD; DS graph; cospectral graphs; incidence graph; subdivision of star
Full Text: PDF
References
Bose, R.C., Shrikhande, S.S., Singhi, N.M.: Edge regular multigraphs and partial geometric designs with an application to the embedding of quasi-regular designs. In: Colloquio Internazionale sulle Teorie Combinatorie, Tomo I, Rome,
1973. Atti dei Convegni Lincei, vol. 17, pp. 49-81. Accad. Naz. Lincei, Rome (1976) Brouwer, A.E.: Small integral trees. Electron. J. Comb. 15, Note 1 (2008) Cameron, P.J.: Research problems from the 19th British Combinatorial Conference. Discrete Math. 293, 313-320 (2005) CrossRef Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001) CrossRef Marrero, O.: Completion and embedding between pseudo (v,k,$λ$)-designs and (v,k,$λ$)-designs. Bull. Am. Math. Soc. 80, 103-105 (1974) CrossRef Marrero, O.: A survey of pseudo (v,k,$λ$)-designs. Aequ. Math. 16, 195-220 (1977) CrossRef Marrero, O., Butson, A.T.: Modular Hadamard matrices and related designs. J. Comb. Theory, Ser. A 15, 257-269 (1973) CrossRef Ryser, H.J.: An extension of a theorem of de Bruijn and Erdös on combinatorial designs. J. Algebra 10, 246-261 (1968) CrossRef Ryser, H.J.: Symmetric designs and related configurations. J. Comb. Theory, Ser. A 12, 98-111 (1972) CrossRef van Dam, E.R., Haemers, W.H.: Which graphs are determined by their spectrum? Linear Algebra Appl. 373, 241-272 (2003) CrossRef van Dam, E.R., Haemers, W.H.: Developments on spectral characterizations of graphs. Discrete Math. 309, 576-586 (2009) CrossRef van Dam, E.R., Spence, E.: Combinatorial designs with two singular values-I: uniform multiplicative designs. J. Comb. Theory, Ser. A 107, 127-142 (2004) CrossRef van Dam, E.R., Spence, E.: Combinatorial designs with two singular values II. Partial geometric designs. Linear Algebra Appl. 396, 303-316 (2005) CrossRef Woodall, D.R.: Square $λ$-linked designs. Proc. Lond. Math. Soc. 20, 669-687 (1970) CrossRef
1973. Atti dei Convegni Lincei, vol. 17, pp. 49-81. Accad. Naz. Lincei, Rome (1976) Brouwer, A.E.: Small integral trees. Electron. J. Comb. 15, Note 1 (2008) Cameron, P.J.: Research problems from the 19th British Combinatorial Conference. Discrete Math. 293, 313-320 (2005) CrossRef Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001) CrossRef Marrero, O.: Completion and embedding between pseudo (v,k,$λ$)-designs and (v,k,$λ$)-designs. Bull. Am. Math. Soc. 80, 103-105 (1974) CrossRef Marrero, O.: A survey of pseudo (v,k,$λ$)-designs. Aequ. Math. 16, 195-220 (1977) CrossRef Marrero, O., Butson, A.T.: Modular Hadamard matrices and related designs. J. Comb. Theory, Ser. A 15, 257-269 (1973) CrossRef Ryser, H.J.: An extension of a theorem of de Bruijn and Erdös on combinatorial designs. J. Algebra 10, 246-261 (1968) CrossRef Ryser, H.J.: Symmetric designs and related configurations. J. Comb. Theory, Ser. A 12, 98-111 (1972) CrossRef van Dam, E.R., Haemers, W.H.: Which graphs are determined by their spectrum? Linear Algebra Appl. 373, 241-272 (2003) CrossRef van Dam, E.R., Haemers, W.H.: Developments on spectral characterizations of graphs. Discrete Math. 309, 576-586 (2009) CrossRef van Dam, E.R., Spence, E.: Combinatorial designs with two singular values-I: uniform multiplicative designs. J. Comb. Theory, Ser. A 107, 127-142 (2004) CrossRef van Dam, E.R., Spence, E.: Combinatorial designs with two singular values II. Partial geometric designs. Linear Algebra Appl. 396, 303-316 (2005) CrossRef Woodall, D.R.: Square $λ$-linked designs. Proc. Lond. Math. Soc. 20, 669-687 (1970) CrossRef