#This code finds co-diamond-free and 2K_3+e-free connected graphs of order 9 without duplicate vertices which has no known existence of skew realization of rank<=4. M=open(DATA+'GraphsOn9VerticesData.txt','U') #It contains a co-diamond-free and 2K_3+e-free connected graph G of order 9 without duplicate vertices , then rank 4 skew realization S of its induced subgraph of order 8, then left null basis matrix N of S and then indices of minimal dependency columns of N. V=[] #V will contain graphs whose rank 4 skew realization is produced from 8 by 8 skew-symmetric matrix of rank<=4 stored in line 4i-2 of the input file i=0 for line in M: if(i % 4 ==1): S=matrix(eval(line)) G = Graph() H = Graph() #A=matrix(1+S.ncols()) #A is 9 by 9 matrix whose principal 8 by 8 submatrix is the adjacency matrix of the graph of S. for p in range(S.ncols()): for q in range(S.ncols()): if (S[p,q] !=0): #A[p,q]=1 G.add_edge(p,q) H.add_edge(p,q) #Here G=H which is the graph of S. if(i % 4 ==3): smc=eval(line) #smc=line.strip('\n') w=Set([]) for j in range(len(smc)): w=w+Set(smc[j]) #w is the union of indices of minimal dependent columns of Left Null space basis matrix of S #print 'w=', w for r in range(1+S.ncols()): if (r in w): #A[r,-1+A.ncols()]=1 #A[-1+A.ncols(),r]=1 G.add_edge(r,S.ncols()) #G becomes graph on vertices 0,1,...,8 obtained from H(=graph of S) by #appending vertex 8 with N(8)=w, the union of minimal dependent columns of LNS basis matrix of S if(S.rank()<=4): V.append(G.graph6_string()) #The function nobarbell evaluated at a graph G returns true if G has no duplicate vertices and no induced 2K_3+e, otherwise it returns false. def nobarbell(G): A=G.adjacency_matrix() n=G.order() setn=[] for i in range(n): setn.append(i) #print setn #T is the set of all 6-subsets of row-indices T=Subsets(setn,6,submultiset=True) nodup=true #Check for duplicate vertices for i in range(-1+n): for j in range(i+1,n): if (G.neighbors(i)==G.neighbors(j)): nodup=false break #If there are no duplicate vertices, then check each induced subgraph on 6 vertices to see if it is a 2K_3 +e h=true if (nodup): m=0 while (m=4): degree=false C=B*B D=B*C #C=B^2, D=B^3. The following checks if G[B] has degree sum =14 and exactly two induced triangles. # Note that (trace of B^2)=(sum of square of eigenvalues of B)=(degree sum of G[B]) and also #(trace of B^3)=(sum of cube of eigenvalues of B)=6*(the number of induced triangles of G[B]). if (degree and ((C.trace() == 14) and D.trace() == 12)): h=false #print '2K_3+e at', x #G.show() m=m+1 if(nodup==true and h==true): return true else: return false