tres Laplacian

4117 days ago by butler

def test_graph(g): """ Given a graph g determines if the sum of the three largest eigenvalues of the laplacian is <= number of edges of g. """ M=g.laplacian_matrix().eigenvalues() M.sort() return M[-1]+M[-2]+M[-3] <= g.size() 
       
""" We want to limit ourselves to sparse graphs. So for this calculation we assume that #edges <= #vertices we also check that the graphs are not subgraphs of something already on our list (i.e., throw out redundant graphs). """ good_graphs=[] for n in [9,10,11,12]: print "Working on "+str(n)+" vertex graphs" for e in range(floor((n+1)/2),n+1): print " Working on "+str(e)+" edges" for g in graphs.nauty_geng(str(n)+" "+str(e)+" -d1"): if test_graph(g): for x in good_graphs: if g.subgraph_search_count(Graph(x)): break else: good_graphs.append(g.graph6_string()) print " "+g.graph6_string() print good_graphs 
        
Working on 9 vertex graphs
   Working on 5 edges
   Working on 6 edges
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      HCOcaOc
Working on 10 vertex graphs
   Working on 5 edges
   Working on 6 edges
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
   Working on 10 edges
      I?`CQGoK?
Working on 11 vertex graphs
   Working on 6 edges
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      J?AA@ACEAC?
   Working on 10 edges
      J?AACGoI?o?
   Working on 11 edges
      J??CCD_F?w?
      J?ACJ@_E?o?
      J?ACJ@OI?o?
Working on 12 vertex graphs
   Working on 6 edges
      K??CA?_C?O?_
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      K???C@_E?KOG
      K?AA@?OACGGO
   Working on 10 edges
      K???EA_E?KK?
      K??CAAAK?WE?
   Working on 11 edges
      K??CA?___wB_
      K??CAAAW?oB_
      K??CAAAK@OI_
      K??CE@_K?WAO
      K?AA@?O`AOF?
      K?AA@AODAO@O
      K?AA@ACS@OAO
      K?AA@ACS?o@O
   Working on 12 edges
      K???C@_FCEKC
      K???CA@[?[OK
      K???EB?K?[@o
      K???EB?K?[EA
      K??CAA_G_wIG
      K??CAAAW?wOS
      K??CAAAK@oE_
      K??CE@_G_oA`
      K??CE@AK@OB_
      K??CE@AK?WF?
      K??CE@AK?WEA
      K??CE@AK?WDA
      K??CB@_c?WM?
      K??CB@Oa?WOo
      K??CCD_S?WOW
      K?AA@AODAOKO
      K?AAD?cS?o@O
['HCOcaOc', 'I?`CQGoK?', 'J?AA@ACEAC?', 'J?AACGoI?o?', 'J??CCD_F?w?',
'J?ACJ@_E?o?', 'J?ACJ@OI?o?', 'K??CA?_C?O?_', 'K???C@_E?KOG',
'K?AA@?OACGGO', 'K???EA_E?KK?', 'K??CAAAK?WE?', 'K??CA?___wB_',
'K??CAAAW?oB_', 'K??CAAAK@OI_', 'K??CE@_K?WAO', 'K?AA@?O`AOF?',
'K?AA@AODAO@O', 'K?AA@ACS@OAO', 'K?AA@ACS?o@O', 'K???C@_FCEKC',
'K???CA@[?[OK', 'K???EB?K?[@o', 'K???EB?K?[EA', 'K??CAA_G_wIG',
'K??CAAAW?wOS', 'K??CAAAK@oE_', 'K??CE@_G_oA`', 'K??CE@AK@OB_',
'K??CE@AK?WF?', 'K??CE@AK?WEA', 'K??CE@AK?WDA', 'K??CB@_c?WM?',
'K??CB@Oa?WOo', 'K??CCD_S?WOW', 'K?AA@AODAOKO', 'K?AAD?cS?o@O']
Working on 9 vertex graphs
   Working on 5 edges
   Working on 6 edges
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      HCOcaOc
Working on 10 vertex graphs
   Working on 5 edges
   Working on 6 edges
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
   Working on 10 edges
      I?`CQGoK?
Working on 11 vertex graphs
   Working on 6 edges
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      J?AA@ACEAC?
   Working on 10 edges
      J?AACGoI?o?
   Working on 11 edges
      J??CCD_F?w?
      J?ACJ@_E?o?
      J?ACJ@OI?o?
Working on 12 vertex graphs
   Working on 6 edges
      K??CA?_C?O?_
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      K???C@_E?KOG
      K?AA@?OACGGO
   Working on 10 edges
      K???EA_E?KK?
      K??CAAAK?WE?
   Working on 11 edges
      K??CA?___wB_
      K??CAAAW?oB_
      K??CAAAK@OI_
      K??CE@_K?WAO
      K?AA@?O`AOF?
      K?AA@AODAO@O
      K?AA@ACS@OAO
      K?AA@ACS?o@O
   Working on 12 edges
      K???C@_FCEKC
      K???CA@[?[OK
      K???EB?K?[@o
      K???EB?K?[EA
      K??CAA_G_wIG
      K??CAAAW?wOS
      K??CAAAK@oE_
      K??CE@_G_oA`
      K??CE@AK@OB_
      K??CE@AK?WF?
      K??CE@AK?WEA
      K??CE@AK?WDA
      K??CB@_c?WM?
      K??CB@Oa?WOo
      K??CCD_S?WOW
      K?AA@AODAOKO
      K?AAD?cS?o@O
['HCOcaOc', 'I?`CQGoK?', 'J?AA@ACEAC?', 'J?AACGoI?o?', 'J??CCD_F?w?', 'J?ACJ@_E?o?', 'J?ACJ@OI?o?', 'K??CA?_C?O?_', 'K???C@_E?KOG', 'K?AA@?OACGGO', 'K???EA_E?KK?', 'K??CAAAK?WE?', 'K??CA?___wB_', 'K??CAAAW?oB_', 'K??CAAAK@OI_', 'K??CE@_K?WAO', 'K?AA@?O`AOF?', 'K?AA@AODAO@O', 'K?AA@ACS@OAO', 'K?AA@ACS?o@O', 'K???C@_FCEKC', 'K???CA@[?[OK', 'K???EB?K?[@o', 'K???EB?K?[EA', 'K??CAA_G_wIG', 'K??CAAAW?wOS', 'K??CAAAK@oE_', 'K??CE@_G_oA`', 'K??CE@AK@OB_', 'K??CE@AK?WF?', 'K??CE@AK?WEA', 'K??CE@AK?WDA', 'K??CB@_c?WM?', 'K??CB@Oa?WOo', 'K??CCD_S?WOW', 'K?AA@AODAOKO', 'K?AAD?cS?o@O']
for x in good_graphs: G=Graph(x) G.show() 
        

                                
                            

                            
                                

                                    

                                

                            
                                

                                    
                                

                        

                    		
                

            

        

        


    




  
    

    
    






    


        
        
        
            
                
            
            
                
"""
Now we limit ourselves to very sparse graphs.
So for this calculation we assume that 
   #vertices/2 <= #edges <= #vertices/2+5
we also check that the graphs are not subgraphs
of something already on our list (i.e., throw
out redundant graphs).
"""
sparse_good_graphs=[]
for n in [13,14,15,16]:
    print "Working on "+str(n)+" vertex graphs"
    for e in range(floor((n+1)/2),floor(n/2)+5):
        print "   Working on "+str(e)+" edges"
        for g in graphs.nauty_geng(str(n)+" "+str(e)+" -d1"):
            if test_graph(g):
                for x in good_graphs:
                    if g.subgraph_search_count(Graph(x)):
                        break
                else:
                    for x in sparse_good_graphs:
                        if g.subgraph_search_count(Graph(x)):
                            break
                    else:
                        sparse_good_graphs.append(g.graph6_string())
                        print "      "+g.graph6_string()
print sparse_good_graphs 

            
            

            

        

        
        
        

            

                

                    
                               
                    
                    
                        

                            

                                
                                    
Working on 13 vertex graphs
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      L???C@?G?o?o_O
   Working on 10 edges
      L????B?K?W?Wo?
Working on 14 vertex graphs
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      M??????_B?B?@_?W?
   Working on 10 edges
   Working on 11 edges
Working on 15 vertex graphs
   Working on 8 edges
   Working on 9 edges
   Working on 10 edges
   Working on 11 edges
Working on 16 vertex graphs
   Working on 8 edges
   Working on 9 edges
   Working on 10 edges
   Working on 11 edges
   Working on 12 edges
      O???????????w?F??[??w
Traceback (click to the left of this block for traceback)
...
__SAGE__

                                
                            

                            
                                

                                    
Working on 13 vertex graphs
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      L???C@?G?o?o_O
   Working on 10 edges
      L????B?K?W?Wo?
Working on 14 vertex graphs
   Working on 7 edges
   Working on 8 edges
   Working on 9 edges
      M??????_B?B?@_?W?
   Working on 10 edges
   Working on 11 edges
Working on 15 vertex graphs
   Working on 8 edges
   Working on 9 edges
   Working on 10 edges
   Working on 11 edges
Working on 16 vertex graphs
   Working on 8 edges
   Working on 9 edges
   Working on 10 edges
   Working on 11 edges
   Working on 12 edges
      O???????????w?F??[??w
^CTraceback (most recent call last):    out redundant graphs).
  File "", line 1, in <module>
    
  File "/tmp/tmpecGj_n/___code___.py", line 23, in <module>
    if g.subgraph_search_count(Graph(x)):
  File "/home/sage/build/sage-5.4/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 10300, in subgraph_search_count
    return S.cardinality()
  File "generic_graph_pyx.pyx", line 550, in sage.graphs.generic_graph_pyx.SubgraphSearch.cardinality (sage/graphs/generic_graph_pyx.c:5050)
  File "generic_graph_pyx.pyx", line 696, in sage.graphs.generic_graph_pyx.SubgraphSearch.__next__ (sage/graphs/generic_graph_pyx.c:5897)
KeyboardInterrupt
__SAGE__

                                

                            
                                

                                    
                                

                        

                    		
                

            

        

        


    




  
    

    
    






    


        
        
        
            
                
            
            
                
for x in sparse_good_graphs:
    G=Graph(x)
    G.show()