Subcubic census

925 days ago by hthall

Census of all connected subcubic graphs on no more than $20$ vertices for which there is no unique shortest path of length $3$ and

for which at least one edge signing has no monotone shortest path of length $3$.

def signings(G): for spantree in G.spanning_trees(): break # just need the one, any spanning tree will do spanners = spantree.edges() unspan = [] ### Actually, unless G is bipartite, we exclude all but a unicyclic graph with a single odd cycle ### (the sign of whose edge product flips on negation of the whole graph unspan = [] bipartite = True # serves as a flag whether we have found one odd cycle yet for xx in G.edges(): if xx in spanners: continue if bipartite and not spantree.distance(xx[0], xx[1]) % 2: # if this edge bridges the first odd cycle bipartite = False continue # skip adding this to the non-spanners unspan.append((xx[0], xx[1])) A = G.adjacency_matrix() for xx in sxrange(1 << len(unspan), 1 << (len(unspan) + 1)): # for binary strings B = A + 0 for ii, digit in enumerate(xx.binary()[1:]): if digit == '1': B[unspan[ii]] = -1 B[unspan[ii][1], unspan[ii][0]] = -1 yield B 
       
def upper(nn): for ii in range(nn): for jj in range(ii, nn): yield ii, jj def qbound(signmat): nn = signmat.ncols() A = Matrix(ZZ, nn, nn, lambda ii, jj: abs(signmat[ii, jj])) bound = 1 oldmat = A + 1 - A oldsign = signmat + 1 - signmat while True: reach = oldmat * A + oldmat cancel = oldsign * signmat for ii, jj in upper(nn): if reach[ii, jj] and not oldmat[ii, jj]: expanded = True if abs(cancel[ii, jj]) == reach[ii, jj]: bound += 1 break else: return bound oldmat = reach oldsign = cancel def count_q(G, q=3): queues = [qbound(xx) for xx in signings(G)] return len([xx for xx in queues if xx <= q]), len(queues) 
       
census = [[]] for ii in sxrange(1, 15): census.append([]) print("For n = {} :".format(ii)) for G in graphs.nauty_geng("{} -D3 -c".format(ii)): A = G.adjacency_matrix() lens = (A + 1)^3 + 2 for xx in lens: if 1 in xx: break else: q, tot = count_q(G) gname = G.graph6_string() print("{}: {} edges; {}/{} good signs.".format(str([gname])[1:-1], G.size(), q, tot)) if q > 0: census[-1].append(gname) # show(G) for ii in sxrange(15, 21): # Including sub-cubics is slow, and yields nothing more from 15 on census.append([]) print("For {} vertices:".format(ii)) if ii % 2: # No odd cubics, so skip continue for G in graphs.nauty_geng("{} -d3 -D3 -c".format(ii)): A = G.adjacency_matrix() lens = (A + 1)^3 + 2 for xx in lens: if 1 in xx: break else: q, tot = count_q(G) gname = G.graph6_string() print("{}: {} edges; {}/{} good signs.".format(str([gname])[1:-1], G.size(), q, tot)) if q > 0: census[-1].append(gname) # show(G) print('Done.') 
       
WARNING: Output truncated!  
full_output.txt



For n = 1 :
'@': 0 edges; 1/1 good signs.
For n = 2 :
'A_': 1 edges; 1/1 good signs.
For n = 3 :
'BW': 2 edges; 1/1 good signs.
'Bw': 3 edges; 1/1 good signs.
For n = 4 :
'CF': 3 edges; 1/1 good signs.
'CV': 4 edges; 1/1 good signs.
'C]': 4 edges; 2/2 good signs.
'C^': 5 edges; 2/2 good signs.
'C~': 6 edges; 4/4 good signs.
For n = 5 :
'DEw': 5 edges; 1/2 good signs.
'DFw': 6 edges; 4/4 good signs.
'DUW': 5 edges; 1/1 good signs.
'DUw': 6 edges; 2/2 good signs.
'DTw': 6 edges; 1/2 good signs.
'D]w': 7 edges; 4/4 good signs.
For n = 6 :
'E?zO': 6 edges; 1/2 good signs.
'ECxo': 7 edges; 2/2 good signs.
'EEr_': 7 edges; 1/4 good signs.
'EEh_': 6 edges; 1/2 good signs.
'EEj_': 7 edges; 3/4 good signs.
'EEho': 7 edges; 1/2 good signs.
'EEiW': 7 edges; 1/2 good signs.
'EEz_': 8 edges; 7/8 good signs.
'EEzO': 8 edges; 1/4 good signs.
'EFz_': 9 edges; 16/16 good signs.
'EQzO': 8 edges; 2/4 good signs.
'EUZ_': 8 edges; 4/4 good signs.
'EUZO': 8 edges; 4/4 good signs.
'EUxo': 9 edges; 8/8 good signs.
For n = 7 :
'F?re_': 8 edges; 0/4 good signs.
'F?qr_': 8 edges; 1/4 good signs.
'FCR`o': 8 edges; 1/2 good signs.
'FCpv?': 9 edges; 3/4 good signs.
'FCptO': 9 edges; 4/4 good signs.
'FCZf?': 9 edges; 2/8 good signs.
'FCZb_': 9 edges; 1/4 good signs.
'FCZco': 9 edges; 1/4 good signs.
'FCxv?': 10 edges; 8/8 good signs.
'FEhf?': 9 edges; 7/8 good signs.
'FEhe_': 9 edges; 1/4 good signs.
'FEhd_': 9 edges; 2/4 good signs.
'FEhv?': 10 edges; 7/8 good signs.
'FEhuO': 10 edges; 8/8 good signs.
'FQjR_': 10 edges; 2/8 good signs.
For n = 8 :
'G?`vF?': 10 edges; 1/8 good signs.
'G?qbe_': 10 edges; 1/8 good signs.
'G?qb_w': 10 edges; 1/4 good signs.
'G?q`qg': 10 edges; 1/4 good signs.
'G?ovE_': 10 edges; 1/8 good signs.
'G?opuG': 10 edges; 1/8 good signs.
'G?qrf?': 11 edges; 6/16 good signs.

...

'K??E@qcX?wY?': 17 edges; 1/64 good signs.
'K??FEbGL@WB_': 18 edges; 1/128 good signs.
'K??FEagT@WB_': 18 edges; 10/128 good signs.
'K??FEaKY@gB_': 18 edges; 8/128 good signs.
'K??FEaKR@oE_': 18 edges; 18/128 good signs.
'K?AEB`gHcoB_': 18 edges; 1/64 good signs.
'K?AB?rOLDOH_': 17 edges; 1/32 good signs.
'K?ABEagE`gH_': 18 edges; 4/64 good signs.
'K?ABCfGT@oD_': 18 edges; 6/64 good signs.
'K?`@?b_s?U?w': 16 edges; 1/32 good signs.
'K?`@E`gh?sAo': 18 edges; 0/64 good signs.
'K?`@E`gFCKEO': 18 edges; 1/64 good signs.
'K?`@E`gEcKE_': 18 edges; 0/64 good signs.
'K?`@Cr_T?[EO': 18 edges; 0/64 good signs.
For n = 13 :
'L??E@_KiAoK_d?': 18 edges; 1/64 good signs.
'L??E@agX?[J?d?': 19 edges; 1/64 good signs.
'L?AA@_geAo?w@g': 18 edges; 0/64 good signs.
'L?`@?b_s@W@W@o': 19 edges; 1/64 good signs.
For n = 14 :
'M???EAob@SM?D_R??': 20 edges; 1/128 good signs.
'M???EAob@SL?D_T??': 20 edges; 0/128 good signs.
'M???EAob@SJ?D_X??': 20 edges; 0/128 good signs.
'M???FBObBCD_E_D_?': 21 edges; 0/256 good signs.
'M???FBObASF?H_D_?': 21 edges; 2/256 good signs.
'M???FBObASD_D_K_?': 21 edges; 0/256 good signs.
'M???FAW`agD_K_Q_?': 21 edges; 0/256 good signs.
'M?AAD?WsAQEOB_HG?': 21 edges; 1/128 good signs.
For 15 vertices:
For 16 vertices:
'O????B_sCWGWI_E_Cg?i?': 24 edges; 0/512 good signs.
'O????B_eCKIGL?R?CW?U?': 24 edges; 1/512 good signs.
'O????B_eCKIGL?Q_@g@E?': 24 edges; 0/512 good signs.
For 17 vertices:
For 18 vertices:
'Q??????wCoOoSOPG@g@E?IG?Q_?': 27 edges; 0/1024 good signs.
For 19 vertices:
For 20 vertices:
Exception MemoryError: MemoryError() in <object repr() failed>
ignored
Exception MemoryError: MemoryError() in <generator object nauty_geng
at 0x7fbfcc77efa0> ignored
Traceback (click to the left of this block for traceback)
...
MemoryError
WARNING: Output truncated!  
full_output.txt



For n = 1 :
'@': 0 edges; 1/1 good signs.
For n = 2 :
'A_': 1 edges; 1/1 good signs.
For n = 3 :
'BW': 2 edges; 1/1 good signs.
'Bw': 3 edges; 1/1 good signs.
For n = 4 :
'CF': 3 edges; 1/1 good signs.
'CV': 4 edges; 1/1 good signs.
'C]': 4 edges; 2/2 good signs.
'C^': 5 edges; 2/2 good signs.
'C~': 6 edges; 4/4 good signs.
For n = 5 :
'DEw': 5 edges; 1/2 good signs.
'DFw': 6 edges; 4/4 good signs.
'DUW': 5 edges; 1/1 good signs.
'DUw': 6 edges; 2/2 good signs.
'DTw': 6 edges; 1/2 good signs.
'D]w': 7 edges; 4/4 good signs.
For n = 6 :
'E?zO': 6 edges; 1/2 good signs.
'ECxo': 7 edges; 2/2 good signs.
'EEr_': 7 edges; 1/4 good signs.
'EEh_': 6 edges; 1/2 good signs.
'EEj_': 7 edges; 3/4 good signs.
'EEho': 7 edges; 1/2 good signs.
'EEiW': 7 edges; 1/2 good signs.
'EEz_': 8 edges; 7/8 good signs.
'EEzO': 8 edges; 1/4 good signs.
'EFz_': 9 edges; 16/16 good signs.
'EQzO': 8 edges; 2/4 good signs.
'EUZ_': 8 edges; 4/4 good signs.
'EUZO': 8 edges; 4/4 good signs.
'EUxo': 9 edges; 8/8 good signs.
For n = 7 :
'F?re_': 8 edges; 0/4 good signs.
'F?qr_': 8 edges; 1/4 good signs.
'FCR`o': 8 edges; 1/2 good signs.
'FCpv?': 9 edges; 3/4 good signs.
'FCptO': 9 edges; 4/4 good signs.
'FCZf?': 9 edges; 2/8 good signs.
'FCZb_': 9 edges; 1/4 good signs.
'FCZco': 9 edges; 1/4 good signs.
'FCxv?': 10 edges; 8/8 good signs.
'FEhf?': 9 edges; 7/8 good signs.
'FEhe_': 9 edges; 1/4 good signs.
'FEhd_': 9 edges; 2/4 good signs.
'FEhv?': 10 edges; 7/8 good signs.
'FEhuO': 10 edges; 8/8 good signs.
'FQjR_': 10 edges; 2/8 good signs.
For n = 8 :
'G?`vF?': 10 edges; 1/8 good signs.
'G?qbe_': 10 edges; 1/8 good signs.
'G?qb_w': 10 edges; 1/4 good signs.
'G?q`qg': 10 edges; 1/4 good signs.
'G?ovE_': 10 edges; 1/8 good signs.
'G?opuG': 10 edges; 1/8 good signs.
'G?qrf?': 11 edges; 6/16 good signs.

...

'K??E@qcX?wY?': 17 edges; 1/64 good signs.
'K??FEbGL@WB_': 18 edges; 1/128 good signs.
'K??FEagT@WB_': 18 edges; 10/128 good signs.
'K??FEaKY@gB_': 18 edges; 8/128 good signs.
'K??FEaKR@oE_': 18 edges; 18/128 good signs.
'K?AEB`gHcoB_': 18 edges; 1/64 good signs.
'K?AB?rOLDOH_': 17 edges; 1/32 good signs.
'K?ABEagE`gH_': 18 edges; 4/64 good signs.
'K?ABCfGT@oD_': 18 edges; 6/64 good signs.
'K?`@?b_s?U?w': 16 edges; 1/32 good signs.
'K?`@E`gh?sAo': 18 edges; 0/64 good signs.
'K?`@E`gFCKEO': 18 edges; 1/64 good signs.
'K?`@E`gEcKE_': 18 edges; 0/64 good signs.
'K?`@Cr_T?[EO': 18 edges; 0/64 good signs.
For n = 13 :
'L??E@_KiAoK_d?': 18 edges; 1/64 good signs.
'L??E@agX?[J?d?': 19 edges; 1/64 good signs.
'L?AA@_geAo?w@g': 18 edges; 0/64 good signs.
'L?`@?b_s@W@W@o': 19 edges; 1/64 good signs.
For n = 14 :
'M???EAob@SM?D_R??': 20 edges; 1/128 good signs.
'M???EAob@SL?D_T??': 20 edges; 0/128 good signs.
'M???EAob@SJ?D_X??': 20 edges; 0/128 good signs.
'M???FBObBCD_E_D_?': 21 edges; 0/256 good signs.
'M???FBObASF?H_D_?': 21 edges; 2/256 good signs.
'M???FBObASD_D_K_?': 21 edges; 0/256 good signs.
'M???FAW`agD_K_Q_?': 21 edges; 0/256 good signs.
'M?AAD?WsAQEOB_HG?': 21 edges; 1/128 good signs.
For 15 vertices:
For 16 vertices:
'O????B_sCWGWI_E_Cg?i?': 24 edges; 0/512 good signs.
'O????B_eCKIGL?R?CW?U?': 24 edges; 1/512 good signs.
'O????B_eCKIGL?Q_@g@E?': 24 edges; 0/512 good signs.
For 17 vertices:
For 18 vertices:
'Q??????wCoOoSOPG@g@E?IG?Q_?': 27 edges; 0/1024 good signs.
For 19 vertices:
For 20 vertices:
Exception MemoryError: MemoryError() in <object repr() failed> ignored
Exception MemoryError: MemoryError() in <generator object nauty_geng at 0x7fbfcc77efa0> ignored
Traceback (most recent call last):            lens = (A + 1)^3 + 2
  File "", line 1, in <module>
    
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 1590, in _recursive_spanning_trees
    trees.extend(_recursive_spanning_trees(G,forest))
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 1573, in _recursive_spanning_trees
    trees = _recursive_spanning_trees(G,forest)
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 1590, in _recursive_spanning_trees
    trees.extend(_recursive_spanning_trees(G,forest))
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 1564, in _recursive_spanning_trees
    return [forest.copy()]
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 1086, in copy
    data_structure=data_structure)
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 1180, in __init__
    self.add_edges(data.edge_iterator(), loops=loops)
  File "/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 10499, in add_edges
    self._backend.add_edge(u, v, label, self._directed)
MemoryError: failed to allocate 32 bytes
no mem for new parser
MemoryError
# Memory error, but we know the answer from before census[20] = [graphs.DesarguesGraph().graph6_string()] 
       
q2census=[[]] for ii in sxrange(1, 15): # The same calculation for just the q = 2 case q2census.append([]) print("For n = {} :".format(ii)) for G in graphs.nauty_geng("{} -D3 -c".format(ii)): A = G.adjacency_matrix() lens = (A + 1)^2 + 2 for xx in lens: if 1 in xx: break else: q, tot = count_q(G, 2) gname = G.graph6_string() print(" {} ({} edges; {}/{} good signs)".format(str([gname])[1:-1], G.size(), q, tot)) if q > 0: q2census[-1].append(gname) # show(G) print('Done.') 
       
For n = 1 :
    '@' (0 edges; 1/1 good signs)
For n = 2 :
    'A_' (1 edges; 1/1 good signs)
For n = 3 :
    'Bw' (3 edges; 1/1 good signs)
For n = 4 :
    'C]' (4 edges; 1/2 good signs)
    'C^' (5 edges; 1/2 good signs)
    'C~' (6 edges; 4/4 good signs)
For n = 5 :
    'DFw' (6 edges; 0/4 good signs)
    'D]w' (7 edges; 1/4 good signs)
For n = 6 :
    'EEz_' (8 edges; 1/8 good signs)
    'EFz_' (9 edges; 6/16 good signs)
    'EUxo' (9 edges; 1/8 good signs)
For n = 7 :
For n = 8 :
    'G?zTb_' (12 edges; 1/32 good signs)
For n = 9 :
For n = 10 :
For n = 11 :
For n = 12 :
For n = 13 :
For n = 14 :
Done.
For n = 1 :
    '@' (0 edges; 1/1 good signs)
For n = 2 :
    'A_' (1 edges; 1/1 good signs)
For n = 3 :
    'Bw' (3 edges; 1/1 good signs)
For n = 4 :
    'C]' (4 edges; 1/2 good signs)
    'C^' (5 edges; 1/2 good signs)
    'C~' (6 edges; 4/4 good signs)
For n = 5 :
    'DFw' (6 edges; 0/4 good signs)
    'D]w' (7 edges; 1/4 good signs)
For n = 6 :
    'EEz_' (8 edges; 1/8 good signs)
    'EFz_' (9 edges; 6/16 good signs)
    'EUxo' (9 edges; 1/8 good signs)
For n = 7 :
For n = 8 :
    'G?zTb_' (12 edges; 1/32 good signs)
For n = 9 :
For n = 10 :
For n = 11 :
For n = 12 :
For n = 13 :
For n = 14 :
Done.

All connected subcubic graphs on up to $16$ vertices that satisfy combinatorial bounds for $q(G) = 2$:

for ii, xx in enumerate(q2census): if xx: # print("On {} vert{}:".format(ii, 'ices' if ii - 1 else 'ex')) # Omitted because Sage wants to do all the printing before all the plotting for gname in xx: # print(str([gname])[1:-1]) # Show as a string with proper '\\' escaping show(Graph(gname).plot()) # show(gname) # print('---------------------------------------------------------') 
       










All connected subcubic graphs on up to $20$ vertices that satisfy combinatorial bounds for $q(G)=3$:

for ii, xx in enumerate(census): if xx: # print("On {} vert{}:".format(ii, 'ices' if ii - 1 else 'ex')) # Omitted because Sage wants to do all the printing before all the plotting for gname in xx: # print(str([gname])[1:-1]) # Show as a string with proper '\\' escaping show(Graph(gname).plot()) # show(gname) # print('---------------------------------------------------------')