# SageMathCell online # https://sagecell.sagemath.org/?q=dxtpcl # Nine non-isomorphic (3,6)=132 graphs found by F.Comellas 2025. # G3 has lower average distance than tha 132 graph from Exoo (1998) # The variable Gn is the graph in sparse6 format . import networkx as nx G0=Graph(r":~?AC`?E_CL?cR?KMASX@OM`KIb[YbwY_CaAo`_SCcwD@cJdOOBkFcsm@g]bkp?Sn_WNBc@DCTaw]f?@CcQCcDECW`wTcgy_O|_sQE?vdc]C?lf@@aobdWmEKMB{UB?xb[zaKVaCtEseHcPCW~`_LBcGBKeDXH_wvhPM_Wv__if_}a`S`@HcGfckR`GNF[aDlKJsJCL@H[VJ[KHTBI{~Ik^JP`_X^dGnI[qHh[ePCHCDJH[`OgJ[hKclIHl_?PEcWKShK\feHEmPrmCTKCEIs_ECkHDwNLsMlyN\uMx{mHtaXqNstJDJKi?_wJa?dOV") G1=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKQCSbccXCke_gfdC^DKid[kaWldsneC\EKqe[cEctesjE{wawxfSpF[{`K}cg~gD@gSnG[KGcBGkuGtFhC|HKOHShH\KgXLhsZH|OexPiSNI\SgK]IsTI|GjLYhxZcP[fX\_`]ih^kClKKYKTHK\ccHdktRK{oLCfLLYLTj`PkkHle`mhhnapomKAMS~M[kMdZMkMMsrM{ENDxgPyfHz_@kNddNTfMP}j@XihUOCGIK|FqA") G2=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKQCSbccXCke_gfdC^DKid[mAWldsneC\EKqe[cEctesjE{wawxfSpF[{`K}cg~gD@gTB``C_XDepEg|GfhHa@IdHJhdBHlMbXN`@OexPiSNI\SgK]IsTI|GJDXjTNJ[aJczJkCJtTJ|_dh`bPahHbkc`KleiXfe@gcxhjPil[ILd`LksLtLL{UMDp_Pqfxrd`sjXt`pueXv_pwnLANSxN[?L`{khykxqNskDknGa?fg}ihUOV") G3=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKQCSbccXCke_gfdC^DKid[mAWldsneC\eSrc_sekudWvfCVFKyeGzfcHFk}cg~gD@gSnG[KGcBGkuGtFhC|HKOHShhdBHlMbXN`@OexPiSNI\SgK]IsTI|GJDXjTNJ[aJczJkCJtTJ|_dh`bPahHbkc`KleiXfe@gcxhjPil[ILd`LksLtLL{UMDp_Pqfxrd`sjXt`pueXv_pwnLANSxN[?L`{khykxqNskDlTIq?hXKeGqOV") G4=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKQCSbccXCke_gfdC^DKid[kaWldsneC\EKqe[cEctesjE{wawxfSpF[{`G|fsdF|?gLAdxB``C_XDepEg|GfhHa@IdHJhdBHlOBXN`@OexPiSNI\SgHTbpUahVh@WjLYhxZcP[fX\_`]ih^kClKKYhHbkc`KleiXfe@gcxhjPilgILd`LksLtLL{UMDp_Pqfxrd`sj[MMsrM{ENDdNLAfHz_@kNdjLdfMP}mhunPzODMH|aKYA") G5=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKQCSbccXCke_gfdC^DKid[kaWldsneC\EKqe[cEctesjfCVFKyeGzfcHFk}f|?gLAdxB``C_XDepEg|GfhHa@IdHJhdBHlOBXN`@OexPiSNI\SgHTbpUahVh@WjLYhxZcP[fX\_`]ih^kClKKYhHbkc`KleiXfe@gcxhjPilgILd`LksLtLL{UMDp_Pqfxrd`sjXt`pueXv_pwkhxgPyfHz_@kNdjLdfMP}hpNkPbOCdGCvFAA") G6=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKac[cbGdcsDC{gbwhdSjdcRDkmd{obgpeSrc_sekudWvfCVFKyeGzfcHFk}cg~gD@gSnG[KGcBGkug|GfhHa@IdHJhdBHlOBXN`@OexPiSNI\SgHTbpUahVh@WjLYhxZcP[fX\_`]ih^kClKKYhHbkc`KleiXfe@gcxhjPilgILd`LksLtLL{UMDp_Pqfxrd`sjXt`pueXv_pwkhxgPyfHz_@kNdjLdfMP}hpNkPbOCQC\EGyA") G7=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKQCSbccXCke_gfdC^DKid[kaWldsneC\EKqe[cEctesjfCVFKyeGzfcHFk}f|?gLAdxB``C_XDepEg|GfhHa@IdHJhdBHlOBXN`@OexPiSNI\SgHTbpUahVh@WjLYhxZcP[fX\_`]ih^kClKKYhHbkc`KleiXfe@gcxhjPilgILd`LksLtLL{UMDp_Pqfxrd`sjXt`pueXv_pwkhxgPyfHz_@kNdjLdfMP}ewwhpNOCdGDaKYA") G8=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bsJB{_cKQCSbccXCke_gfdC^DKid[kaWldsneC\EKqe[cEcvEsjE{wawxfSpF[{`G|fsdF|?gLAdxB``C_XDepEg|GfhHa@IdHJhdBHlMbXN`@OexPiSNI\SgHTbpUahVh@WjLYhxZcP[fX\_`]ih^kClbPahHbkc`KleiXfe@gcxhlTj`PkkHle`mhhnapokxp_Pqfxrd`sjXt`srM{ENDdgPyfHz_@kmpvn`|NtYL\xNQ?egukHaOV") G9=Graph(r":~?AC_C@_SB_cD_sF`CH`SJ`cL`sN_?OaKQ_wRacTasLA{WbKY_GZbc\bs^cC`aOac[cbGdcsDC{gb{id[kaWldsneC\EKqe[cEctesjE{wawxfSpF[{`G|fsdF|?gLAdxB``C_XDepEg|GfhHa@IdHJhdBHlMbXN`@Oe|Q`xRid@Ik]IsTI|GJDXjTNJ[aJczJkCJtTJ|_dh`bPahHbkc`KleiXfeCfLLYLTj`PkkHle`mhhnapokxp_Pqfxrd`sjXt`pueXv_pwklANSxN[?LdxNT{Nh}iHQl@hOCJCChDQA") # List of graphs to process graphs = [('Exoo ', G0),('Graph 1 ', G1),('Graph 2 ', G2),('Graph 3 ', G3),('Graph 4 ', G4),('Graph 5 ', G5),('Graph 6 ', G6),('Graph 7 ', G7),('Graph 8 ', G8),('Graph 9 ', G9)] def check_all_isomorphisms(graph_list): n = len(graph_list) print("\nIsomorphism check of all pairs (a dot means non isomorphic):") for i in range(n): label_i, G_i = graph_list[i] for j in range(i + 1, n): label_j, G_j = graph_list[j] if G_i.is_isomorphic(G_j): print(f"\n{label_i} is isomorphic to {label_j}") else: print(".", end="") print() # Newline at the end def count_k_cycles(G, k): count = 0 visited = set() def dfs(path, start, depth): nonlocal count current = path[-1] # Early exit if we?re going too deep if depth == k: if start in G.neighbors(current): # Normalize to avoid duplicates cycle = tuple(sorted(path)) if cycle not in visited: visited.add(cycle) count += 1 return for neighbor in G.neighbors(current): if neighbor not in path and neighbor >= start: dfs(path + [neighbor], start, depth + 1) for v in G.vertices(): dfs([v], v, 1) return count # each cycle counted twice (once forward, once reverse) def algebraic_connectivity(G): """ Compute the algebraic connectivity (Fiedler value) of a graph G. INPUT: - G: a SageMath Graph OUTPUT: - The second-smallest eigenvalue of the Laplacian matrix of G """ L = G.laplacian_matrix() eigenvalues = L.eigenvalues() eigenvalues.sort() if len(eigenvalues) < 2: return 0 # Trivial case: empty or isolated vertex graph return eigenvalues[1] def domination_number(G): """ Compute the domination number of a graph G using MILP. INPUT: - G: a SageMath Graph OUTPUT: - The domination number (integer) """ p = MixedIntegerLinearProgram(maximization=False) x = p.new_variable(binary=True) # Objective: minimize the number of chosen vertices p.set_objective(sum(x[v] for v in G.vertices())) # Constraint: each vertex is dominated for v in G.vertices(): p.add_constraint(x[v] + sum(x[u] for u in G.neighbors(v)) >= 1) return p.solve() # Print properties for each graph in the list print("\nMain properties of the graphs\n") for label, graph in graphs: print(f"{label} | Ord.: {graph.order()} / Size: {graph.size()} / 3reg.? {graph.is_regular(k=3)} " f" / Girth: {graph.girth()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} / Alg.conn. {algebraic_connectivity(graph).n(digits=6)} Dom.num.: {domination_number(graph)}") print("\nSymmetry properties of the graphs\n") for label, graph in graphs: print(f"{label} | Aut.group.ord.: {graph.automorphism_group().order()} / Cayley ? {graph.is_cayley()} -- vtx.trans. ? {graph.is_vertex_transitive()} -- edge.trans. ? {graph.is_edge_transitive()}" ) # Check isomorphisms # print(f"Are isomorphic G5 and G6? {G5.is_isomorphic(G6)}") check_all_isomorphisms(graphs) # Compute the distance distribution from a given vertex v in graph G # Returns a list where the i-th element is the number of vertices at distance i from v def distance_distribution(G, v): from collections import Counter distances = G.shortest_path_lengths(v) distribution = Counter(distances.values()) result = [distribution[d] for d in sorted(distribution)] return result print("\nDistance distribution from vertex 0") for label, graph in graphs: print(f"{label} distance distrib: {distance_distribution(graph, 0)}") # Counting k-cycles for each graph print("\nNumber of k-cycles for k=3 up to 15") for label, graph in graphs: print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 16))) G1nx = G1.networkx_graph() G2nx = G2.networkx_graph() G3nx = G3.networkx_graph() G4nx = G4.networkx_graph() G5nx = G5.networkx_graph() G6nx = G6.networkx_graph() G7nx = G7.networkx_graph() G8nx = G8.networkx_graph() G9nx = G9.networkx_graph() # Write to adjacency list format nx.write_adjlist(G1nx,"132_G1_adjlist.txt") nx.write_adjlist(G2nx,"132_G2_adjlist.txt") nx.write_adjlist(G3nx,"132_G3_adjlist.txt") nx.write_adjlist(G4nx,"132_G4_adjlist.txt") nx.write_adjlist(G5nx,"132_G5_adjlist.txt") nx.write_adjlist(G6nx,"132_G6_adjlist.txt") nx.write_adjlist(G7nx,"132_G7_adjlist.txt") nx.write_adjlist(G8nx,"132_G8_adjlist.txt") nx.write_adjlist(G9nx,"132_G9_adjlist.txt") print("\n") ## """ OUTPUT Main properties of the graphs Exoo | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 6 / Diam.: 6 / Avg.dist: 4.72149 / Alg.conn. 0.437172 Dom.num.: 35.0 Graph 1 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 5 / Diam.: 6 / Avg.dist: 4.72415 / Alg.conn. 0.415114 Dom.num.: 36.0 Graph 2 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 5 / Diam.: 6 / Avg.dist: 4.72276 / Alg.conn. 0.419280 Dom.num.: 36.0 Graph 3 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 5 / Diam.: 6 / Avg.dist: 4.72137 / Alg.conn. 0.422815 Dom.num.: 35.0 Graph 4 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 7 / Diam.: 6 / Avg.dist: 4.71536 / Alg.conn. 0.444035 Dom.num.: 36.0 Graph 5 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 7 / Diam.: 6 / Avg.dist: 4.71999 / Alg.conn. 0.444035 Dom.num.: 35.0 Graph 6 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 7 / Diam.: 6 / Avg.dist: 4.71999 / Alg.conn. 0.444035 Dom.num.: 35.0 Graph 7 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 7 / Diam.: 6 / Avg.dist: 4.71999 / Alg.conn. 0.444035 Dom.num.: 35.0 Graph 8 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 7 / Diam.: 6 / Avg.dist: 4.71443 / Alg.conn. 0.423029 Dom.num.: 36.0 Graph 9 | Ord.: 132 / Size: 198 / 3reg.? True / Girth: 5 / Diam.: 6 / Avg.dist: 4.72415 / Alg.conn. 0.419280 Dom.num.: 36.0 Symmetry properties of the graphs Exoo | Aut.group.ord.: 2 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 1 | Aut.group.ord.: 4 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 2 | Aut.group.ord.: 4 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 3 | Aut.group.ord.: 2 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 4 | Aut.group.ord.: 4 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 5 | Aut.group.ord.: 4 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 6 | Aut.group.ord.: 12 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 7 | Aut.group.ord.: 6 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 8 | Aut.group.ord.: 4 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Graph 9 | Aut.group.ord.: 12 / Cayley ? False -- vtx.trans. ? False -- edge.trans. ? False Isomorphism check of all pairs (a dot means non isomorphic): ............................................. Distance distribution from vertex 0 Exoo distance distrib: [1, 3, 6, 12, 24, 48, 38] Graph 1 distance distrib: [1, 3, 6, 12, 24, 48, 38] Graph 2 distance distrib: [1, 3, 6, 12, 24, 48, 38] Graph 3 distance distrib: [1, 3, 6, 12, 24, 47, 39] Graph 4 distance distrib: [1, 3, 6, 12, 24, 46, 40] Graph 5 distance distrib: [1, 3, 6, 12, 24, 46, 40] Graph 6 distance distrib: [1, 3, 6, 12, 24, 44, 42] Graph 7 distance distrib: [1, 3, 6, 12, 24, 46, 40] Graph 8 distance distrib: [1, 3, 6, 12, 24, 45, 41] Graph 9 distance distrib: [1, 3, 6, 12, 24, 46, 40] Number of k-cycles for k=3 up to 10 Exoo 0 0 0 1 2 0 4 12 16 676 396 676 534 Graph 1 0 0 3 0 0 0 0 0 24 708 348 726 486 Graph 2 0 0 2 0 1 0 2 4 20 698 364 710 500 Graph 3 0 0 1 0 2 0 4 8 16 688 380 694 514 Graph 4 0 0 0 0 3 0 6 4 20 706 356 706 474 Graph 5 0 0 0 0 3 0 6 12 12 678 396 678 528 Graph 6 0 0 0 0 3 0 6 12 12 678 396 678 528 Graph 7 0 0 0 0 3 0 6 12 12 678 396 678 528 Graph 8 0 0 0 0 1 0 10 10 16 697 360 710 454 Graph 9 0 0 3 0 0 0 0 0 24 708 348 726 486 132_G1_adjlist.txt [Updated 0 time(s)] 132_G2_adjlist.txt [Updated 0 time(s)] 132_G3_adjlist.txt [Updated 0 time(s)] 132_G4_adjlist.txt [Updated 0 time(s)] 132_G5_adjlist.txt [Updated 0 time(s)] 132_G6_adjlist.txt [Updated 0 time(s)] 132_G7_adjlist.txt [Updated 0 time(s)] 132_G8_adjlist.txt [Updated 0 time(s)] 132_G9_adjlist.txt [Updated 0 time(s)] """