[PDF] [PDF] Bipartite graphs with five eigenvalues and pseudo designs - EMIS

[PDF] BIPARTITE GRAPHS OBTAINED FROM ADJACENCY MATRICES

thought of as the adjacency matrix of a bipartite graph B(G) of order 2n, where the rows and columns correspond to the bipartition of B(G) For agraph H, let k(H) 

[PDF] Solution (#1027) Let A be the adjacency matrix of a bipartite graph

Solution (#1027) Let A be the adjacency matrix of a bipartite graph with vertices v1, ,vn As the graph is bipartite we can partition the vertex set into disjoint 

[PDF] Package birankr

23 mar 2020 · Must contain bipartite graph data, either for- matted as an or input data is classed as an adjacency matrix, returns a vector of node ranks

[PDF] Using bipartite to describe and plot two-mode networks in R

Figure 1: A bipartite graph of Motten's (1982) pollination network (top) and a visualisation of the adjacency matrix (bottom) The darker a cell is represented, the 

[PDF] Spectra of Simple Graphs - Whitman College

13 mai 2013 · An example Bipartite graph on 6 vertices: 1 2 3 4 5 6 Figure 2 4 Bipartite Graph The general form for the adjacency matrix of a bipartite 

[PDF] Bipartite graphs with five eigenvalues and pseudo designs - EMIS

3 déc 2011 · graph resulting from adding a new vertex to Lk,k and joining all vertices of one part of it to the new vertex The adjacency matrix of a bipartite 

[PDF] 1 Introduction - Virginia Commonwealth University

Suppose H is a bipartite graph with bipartite adjacency matrix B Then H has property π if and only if there are permutation matrices S and R for which SBR = BT

[PDF] On the adjacency matrix of a block graph - Indico

Characterize nonsingular block graphs Page 18 Adjacency matrix over GF(2) Lemma Let G be a graph 

[PDF] On the Determinant of the Adjacency Matrix of a Type of Plane

the algebraic structure count of bipartite graphs) see for example [1,3,7,11,12] ( resp [3,8–10]) A polyomino system is a finite 2-connected plane graph such that  

[PDF] bipartite graph algorithm dfs

[PDF] bipartite graph definition with example

[PDF] bipartite graph example pdf

[PDF] bipartite graph worksheet

[PDF] bird on australian 50 cent coin

[PDF] birth rates in europe by country

[PDF] birthday reminder android app source code

[PDF] bis exchange rate index

[PDF] bit masking in c geeksforgeeks

[PDF] bitcoin pdf 2020

[PDF] bitcoin price

[PDF] bitcoin sovereignty through mathematics pdf

[PDF] bitwise and operators in c

[PDF] bitwise operators in c with examples

[PDF] bitwise operators in c with examples ppt

J Algebr Comb (2012) 36:209-221

DOI 10.1007/s10801-011-0331-3

Bipartite graphs with five eigenvalues and pseudo

designs

Ebrahim Ghorbani

Received: 20 November 2010 / Accepted: 11 November 2011 / Published online: 3 December 2011

© Springer Science+Business Media, LLC 2011

AbstractA pseudo(v,k,λ)-design is a pair(X,B), whereXis av-set, andB= {B 1 ,...,B v-1 }is a collection ofk-subsets (blocks) ofXsuch that any two distinct B i ,B j signs to characterize graphs of ordernwhose (adjacency) spectrum contains zero and

±θwith multiplicity(n

2. Meanwhile, partial results con-

firming a conjecture of O. Marrero on a characterization of pseudo(v,k,λ)-designs are obtained. KeywordsSpectrum of graph·Pseudo design·BIBD·DS graph·Cospectral graphs·Incidence graph·Subdivision of star1 Introduction To study bipartite graphs with four/five distinct (adjacency) eigenvalues, one needs to investigate combinatorial designs with two singular values (i.e., the matrixNN has only two positive eigenvalues, whereNis the(0,1)-incidence matrix of the design). Recently, van Dam and Spence [12] studied bipartite graphs with four eigenvalues which are precisely the incidence graphs of designs with two singular values with introduced by Ryser [9]. In [13], bipartite biregular graphs with five distinct eigenval- ues were investigated. These graphs correspond to designs with two singular values,

E. Ghorbani (?)

Department of Mathematics, K.N. Toosi University of Technology, P.O. Box 16315-1618,

Tehran, Iran

e-mail:e_ghorbani@ipm.ir

E. Ghorbani

School of Mathematics, Institute for Research in Fundamental Sciences (IPM),

P.O. Box 19395-5746, Tehran, Iran

210 J Algebr Comb (2012) 36:209-221

constant block size and constant replication number. These designs are called partial geometric designs, first introduced by Bose (see [1]). Designs with few distinct sin- gular values are also of interest from statistical point of view. R.A. Bailey (cf. [3]) recently raised the question of which designs have three eigenvalues. To be more spe- cific, it was asked for which designs with constant block size, constant replication, and incidence matrixN, doesNN have three distinct eigenvalues. In this paper, we continue this line by studying bipartite graphs with five eigen- values where the second largest eigenvalue is relatively small. To be more precise, we characterize the graphs withnvertices whose spectrum contains{0,(±θ) n-3 2

2. The restriction to⎷2 comes from our limited knowledge of the

corresponding designs. Having enough information of related designs, one can char- acterize the graphs with largerθ. As it will be explained in the next section, it follows thatθmust be a square root of an integer. So the next possibleθis⎷ 3. The graphs withnvertices whose spectrum contains(±θ) n-2 2 were already characterized by van Dam and Spence [12]. Note that the incidence graphs of symmetric(v,k,λ)-designs are precisely the regular graphs with the re- quired property andθ=⎷ k-λ. The graphs of the subject of the paper have a close connection with a family of combinatorial designs called pseudo designs. Therefore, we first study pseudo de- signs following Marrero [5,6] and Woodall [14]. Our investigation has some im- plications on a conjecture of Marrero on a characterization of pseudo designs. We then make use of these results to determine the families of graphs whose spectrum contains{0,(±θ) n-3 2 By means of the spectral characterization of the aforementioned graphs, we find some new families of graphs which are DS (i.e., determined by spectrum). Finding new families of DS graphs is one of the challenging and very active research subjects in spectral graph theory. For more about DS graphs, see the surveys [10,11].

2 Preliminaries

All the graphs we consider in this paper are finite, simple, and undirected. Theorder of a graphGis the number of vertices ofG. By the eigenvalues ofGwe mean those of its adjacency matrix. ThespectrumofGis the multiset of eigenvalues ofG.The ofG. We denote byS 2k+1 the subdivision of the starK 1,k . The complete bipartite graphK k,k minus a perfect matching is denoted byL k,k . We denote byH k,k+1 the graph resulting from adding a new vertex toL k,k and joining all vertices of one part of it to the new vertex. The adjacency matrix of a bipartite graphGcan be rearranged so that it has the form?ON N O? with square zero matricesO. We denote byJ r,? the all-1 matrix withrrows and? columns, and byJ r if it is a square matrix. When the order of the matrix is clear from the context, we drop the subscripts. The matrixNis called thebipartite adja- cency matrixofG. The bipartite graphs of ordern=2k+1 with bipartite adjacency

J Algebr Comb (2012) 36:209-221 211

Fig. 1The graphsR

13 (left)andQ 13 (right) matrices?I k-3 J O ?I 3 k×(k+1) ,??I k-3 J OJ 3 -I 3 k×(k+1) are denoted byR n andQ n , respectively, where?I is the matrix resulting from ex- tending the identity matrix by an all-1 column vector, i.e., I =(I 1

The graphsR

13 andQ 13 are depicted in Fig.1. Acombinatorial designis a pair(X,B), whereXis a set of points, andBis a collection of subsets ofX, called blocks, together with an incidence relation between the points and the blocks. Abalanced incomplete block designBIBD(b,v,r,k,λ)is a combinatorial design withvpoints andbblocks all of which have the same size kand the incidence relation that any 2-subset ofXis contained in exactlyλblocks numberrof blocks. Necessary conditions for the existence of a BIBD(b,v,r,k,λ) are vr=bk,(1) r(k-1)=λ(v-1).(2) ABIBD(b,v,r,k,λ)withb=v(and sor=k) is called a symmetric(v,k,λ)- design. It is known that in a symmetric(v,k,λ)-design two distinct blocksB i ,B j whereXis av-set, andB={B 1 ,...,B v-1 }is a collection ofk-subsets (blocks) of

Xsuch that any two distinctB

i ,B j Each combinatorial design is completely determined by its correspondingincidence matrix;thisisthe(0,1)-matrixA=(a ij )whose rows and columns are indexed by the blocks and the points of the design, respectively, wherea ij =1ifx j ?B i and a ij =0ifx j ??B i .Theincidence graphof a designDis a bipartite graph such that its bipartite adjacency matrix is the incidence matrix ofD. RemarkIn order to avoid trivial cases, we assume that the designs considered in this paper (and so their incidence graphs) are connected. Therefore, the Perron-Frobenius theorem (cf. [4, p. 178]) can be applied. It follows that the largest singular value has multiplicity one and a positive eigenvector. Another consequence is that ifNis the bipartite adjacency matrix of a connected bipartite graph of ordernwith five distinct eigenvalues where the zero eigenvalue is of multiplicity 1, then the characteristic polynomial ofNN is of the formx(x 2 -a) n-3 2 (x 2 -b). As mentioned in [12], it

212 J Algebr Comb (2012) 36:209-221

turns out that ifn>5, thenaandbmust be integers. Forn=5, there are only two such graphs with the following bipartite adjacency matrices: ?111 001? and?111 011?

The spectra of these two graphs are{0,±?

2±⎷2}and{0,±

1 2

10±2⎷17},re-

2 and{0,(±θ)

n-3 2 }is contained in the spectrum of a graph of ordern>5, thenθ=1orθ=⎷ 2.

3 Pseudo(v,k,λ)-designs

Pseudo designs were studied by Marrero [5,6] and Woodall [14]. Woodall used an- other terminology; he called pseudo designsnear-squareλ-linked designs. 1

We fol-

low the terminology of Marrero. A pseudo(v,k,λ)-design is calledprimaryifvλ?=k 2 and is callednonprimary whenvλ=k 2 .In[7] it is shown that in a nonprimary pseudo design,v=2k.Thus,a pseudo(v,k,λ)-design is nonprimary if and only ifv=4λandk=2λ. The existence of a nonprimary pseudo(v,k,λ)-design is equivalent to the exis- tence of an Hadamard design: Theorem 1(Marrero-Butson [7])The incidence matrix of a given pseudo (4λ,2λ,λ)-design can always be obtained from the incidence matrixAof a sym- metric(4λ-1,2λ-1,λ-1)-design by adjoining one column of all1stoAand then possibly complementing some rows ofA. In the theorem, complementing a row means that 0s and 1s are interchanged in that row. For example, take the Fano plane which is the unique symmetric(7,3,1)- design with points{1,...,7}and blocks{124,235,346,457,156,267,137}.Now the theorem asserts that by adding a new point to all the blocks, namely 8, and complementing any set of blocks we get a pseudo(8,4,2 )-design. For exam- ple, if we do this for the first block, we have the pseudo design with blocks {3567,2358,3468,4578,1568,2678,1378}. For primary pseudo designs, we have the following: Theorem 2(Marrero [5,6])The incidence matrixAof a primary pseudo(v,k,λ)- designDcan be obtained from the incidence matrix of a symmetric(¯v,¯k,¯λ)-design wheneverDsatisfies one of the following arithmetical conditions on its parameters. (i)If(k-1)(k-2)=(λ-1)(v-2),thenAis obtained by adjoining a column of

1s to the incidence matrix of a symmetric(v-1,k-1,λ-1)-design.

(ii)Ifk(k-1)=λ(v-2),thenAis obtained by adjoining a column of0stothe incidence matrix of a symmetric(v,k,λ)-design 1

Asquareλ-linked designconsists ofvpoints andvblocks such that any two distinct blocks intersect in

λelements. This configuration is called aλ-designbyRyser[8] if in addition there exist two blocks of

different sizes.

J Algebr Comb (2012) 36:209-221 213

(iii)Ifk(k-1)=λ(v-1),thenAis obtained from discarding a row from the inci- dence matrix of a symmetric(v,k,λ)-design. (iv)Ifk=2λ,thenAis obtained from the incidence matrixBof a symmetric (v,k,λ)-design as follows:a row is discarded fromBand then thek columns ofBwhich had a1in the discarded row are complemented(0s and1s are inter- changed in these columns). It was conjectured by Marrero [5,6] that given a primary pseudo(v,k,λ)-design, “completion" or “embedding" between the given pseudo design and some symmetric (¯v,¯k,¯λ)-design is always possible. In other words: Conjecture 3(Marrero [5,6])The parameters of a given primary pseudo(v,k,λ)- design satisfy at least one of the four conditions of Theorem2. He proved the validity of his conjecture forλ=1. Theorem 4(Marrero [6], Woodall [14])LetAbe the incidence matrix of a given primary pseudo(v,k,λ)-design,so thatAhas two distinct column sumss 1 ands 2

Lety=(k+λ(v-2)-ks

2 )/(s 1 -s 2 ),and letfbe the number of columns ofA having the column sums 1 .Then,after an appropriate permutation of the columns of

A,it must be possible to writeA=[M

v-1,f N v-1,v-f ],whereMis the incidence matrix of aBIBD(¯b=v-1,¯v=f,¯r=s 1 ,¯k=y,¯λ=s 1 -k+λ),andNis the incidence matrix of aBIBD(¯b=v-1,¯v=v-f,¯r=s 2 ,¯k=k-y,¯λ=s 2 -k+λ). (Note thatfmay take the values1orv-1,too.) In order to study the graphs of the subject of this paper, we need to characterize pseudo designs withk-λ=1 or 2. For this, we need the following lemma.

Lemma 5LetDbe aBIBD(b,v,r,k,λ).

(i)Ifr=λ+1,thenDis either the symmetric(v,1,0)-design or the symmetric (v,v-1,v-2)-design. (ii)Ifr=λ+2,thenDis one of theBIBD(2v,v,2,1,0),BIBD(6,4,3,2,1),

BIBD(6,3,3,2,2),

the symmetric(7,3,1)-design,or the symmetric(7,4,2)- design. ProofPart (i) is straightforward. We prove (ii). First letb>v.Soλ+1=r-1≥k. By (2),(λ+2)(k-1)=λ(v-1).Ifλ=0, thenr=2 andk=1. So, by (1), b=2v, which means thatDis BIBD(2v,v,2,1,0).Ifλ=1, thenr=3, and so v=3k-2. We havek?=1 since otherwisev=1, which is impossible. Thusk=2.

It turns out that

Dis BIBD(6,4,3,2,1).Ifλ=2, thenr=4, and sov=2k-1. By (1),bk=4(2k-1), from which it follows thatk=2 and thusb=6. HenceDis BIBD(6,3,3,2,2).Letλ≥3. Ifλis odd, thenλ|k-1, and thusλ=k-1. Ifλis even, then 2 |k-1. Sinceλ≥k-1, it follows that eitherk-1=λork-1= 2 the latter is impossible due to (2). Therefore(k+1)(k-1)=(k-1)(v-1),so v=k+2. On the other hand,bk=(k+1)(k+2), which is impossible sincek≥4. Now letb=v.Sor=k=λ+2. We have(λ+2)(λ+1)=λ(v-1). Clearlyλ?=0.

214 J Algebr Comb (2012) 36:209-221

Ifλ=1, thenk=3 andv=7. SoDis the symmetric(7,3,1)-design. Ifλ=2, then k=4 andv=7. SoDis the symmetric(7,4,2)-design.?

Theorem 6LetDbe a pseudo(v,k,λ)-design.

(i)Ifk=λ+1,thenDis obtained from the symmetric(v-1,1,0)-design or the symmetric(v-1,v-2,v-3)-design by either adding an isolated point or a point which belongs to all of the blocks. (ii)Ifk=λ+2,then,up to isomorphism,Dis one of theD i =({1,...,8},B i i=1,2,3,4,where B 1 ={1238,1458,1678,3568,2478,3468,2568}, B 2 ={4567,1458,1678,3568,2478,3468,2568}, B 3 ={4567,2367,1678,3568,2478,3468,2568}, B 4 ={4567,2367,2345,3568,2478,3468,2568}; or is obtained by omitting one block either from the unique symmetric(7,4,2)- design or the unique symmetric(7,3,1)-design. Proof(i) First, letDbe nonprimary. This is the case only ifλ=1, and sok=2, v=4. By Theorem1,Dis obtained from a symmetric(3,1,0)-design by the tech- nique described in Theorem1. Applying this technique, it turns out thatDis either the symmetric(3,1,0)-design with a point added to all of its blocks or the sym- metric(3,2,1)-design with an extra isolated point. Now, letDbe primary. In view of Theorem4,Dis obtained by “pasting" two BIBD(b i =v-1,v i ,r i ,k i i )with r i i +1. Keeping the notation of Theorem4,wemusthavef=1. ThusMis ei- ther the vector0or1, and by Lemma5,Nis the incidence matrix of either symmetric (v-1,1,0)-design or symmetric(v-1,v-2,v-3)-design. (ii) First, letDbe nonprimary. This is the case only ifλ=2, and sok=4,v=8. By Theorem1,Dis obtained from the Fano plane by the technique described in The- orem1. Making use of the Mapleprocedure for checking graph isomorphism, it turns out thatDis isomorphic to one of the pseudo designsD 1 ,D 2 ,D 3 ,orD 4 .Now,let Dbe primary. ThusDis obtained by “pasting" two BIBD(¯b i =v-1,¯v i ,¯r i ,¯k i i )"s with¯r i i +2fori=1,2. Iff=1, thenMis either the vector0or1, and by Lemma5,Nis the incidence matrix of either symmetric(7,3,1)-design or sym- metric(7,4,2)-design. Iff≥2, thenMandNmust be chosen from the incidence matrices of BIBD(6,4,3,2,1),BIBD(6,3,3,2,2),orBIBD(2?-2,?-1,2,1,0) for some?≥2. Since¯v 1 +¯v 2 =v=¯b 1 +1=¯b 2 +1, the only possible choices for

MandNare that either

(1)Mis the incidence matrix of BIBD(6,4,3,2,1), andNis that of BIBD(6,3,3,

2,2);or

(2)Mis the incidence matrix of BIBD(6,4,3,2,1), andNis that of BIBD(2?-

2,?-1,2,1,0)for?=3.

If (1) is the case, thenv=7,s

1 =3,s 2 =4, and so 3k-5λ=y=2, which, together withk-λ=2, givesλ=2 andk=4. Now,Dsatisfies the conditions of parts

J Algebr Comb (2012) 36:209-221 215

(iii) and (iv) of Theorem2. From part (iii) it follows thatDis obtained from the symmetric(7,4,2)-design by omitting one of its blocks; and from part (iv) we see thatD={3567,1467,1257,1236,2347,1345,2456}, which is again the symmetric (7,4,2)-design with an omitted block. If (2) is the case, then(v,k,λ)=(7,3,1), and by Theorem2(iii),Dis obtained from the symmetric(7,3,1)-design by omitting one of its blocks.? Corollary 7Conjecture3holds for pseudo(v,k,λ)-designs withk=λ+1or k=λ+2.

4 Graphs with many±1 eigenvalues

In this section we characterize all graphs of ordernwhose spectrum contains a zero and±1 with multiplicity(n-3)/2. We show that this family of graphs consists of S 2k+1 ,H k,k+1 ,R 2k+1 ,Q 2k+1 , wheren=2k+1, and two graphs of order 13.

We begin by determining the spectrum ofS

n ,L k,k ,H k,k+1 ,R n , andQ n

Lemma 8

(i) spec(S 2k+1 )={±⎷k+1,0,(±1) k-1 (ii) spec(L k,k )={±(k-1),(±1) k-1 (iii) spec(H k,k+1 )={±⎷k 2 -k+1,0,(±1) k-1 }fork≥2, (iv) spec(R 2k+1 )=spec(Q 2k+1 )={±2⎷k-2,0,(±1) k-1 }fork≥3. ProofIf one deletes the vertex of maximum degree fromSquotesdbs_dbs14.pdfusesText_20