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('---------------------------------------------------------')
                                                                                                                                                 
|
|
|