#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()) #Gc=G.canonical_label() #print G.graph6_string() #G.set_pos(G.get_pos()) #G.show(save_pos=True) #print 'Can verify that N(8)=', w #G.delete_vertex(8) #H.set_pos(G.get_pos()) #H.show() i=i+1 #print 'V=', V #Now V contains graphs of order 9 whose rank 4 skew realization exists Unknown=[] #Unknown will contain connected graphs of order 9 without any known rank 4 realization f=open(DATA+'pot9output.txt','U') #pot9output.txt contains all co-diamond-free, 2K_3+e-free connected graphs of order 9 with no duplicate vertices j=0 for p in f: GU=Graph(p) realization=false GV=Graph(V[j]) if(GU.is_isomorphic(GV)): realization=true j=j+1 if(realization==false): Unknown.append(p) print 'Total number of connected graphs of order 9 without known rank 4 realization is' , len(Unknown), '\n' print 'They are following:\n' for t in range(len(Unknown)): print Unknown[t].strip('\n')