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$.
|
|
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 |
|
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$:
|
All connected subcubic graphs on up to $20$ vertices that satisfy combinatorial bounds for $q(G)=3$:
|
|