# SageMathCell online https://sagecell.sagemath.org/?q=uobfwy # (5,4) = 252; Moore bound= 426; # ''' Main properties of the graph rajiv252 | Ord.: 252 / Size: 630 / Diam.: 4 / Avg.dist: 3.50531 / 5-reg.? True / Girth: 3 exoo212 | Ord.: 212 / Size: 530 / Diam.: 4 / Avg.dist: 3.37441 / 5-reg.? True / Girth: 6 Degree histogram exoo212 : [0, 0, 0, 0, 0, 212] Symmetry properties of the graph rajiv252 | Aut.group.ord.: 5040 / Cayley ? False --- vtx.trans. ? False -- edge.trans. ? False exoo212 | Aut.group.ord.: 53 / Cayley ? False --- vtx.trans. ? False -- edge.trans. ? False Automorphism group structure: x means direct product; : means semidirect product. rajiv252 : S7 | center order: 1 exoo212 : C53 | center order: 53 rajiv252 distance distrib from vtx. 0: [1, 5, 20, 70, 156] rajiv252 distance distrib from vtx. 9: [1, 5, 20, 70, 156] exoo212 distance distrib from vtx. 0: [1, 5, 20, 77, 109] exoo212 distance distrib from vtx. 9: [1, 5, 20, 76, 110] Number of k-cycles for k=3 up to 7 rajiv252 35 0 0 140 1260 exoo212 0 0 0 106 1537 ''' import networkx as nx rajiv252 = Graph(r":~?B{e_id[kdk}DOsdsneCwfKyh?jEkmF{peSwGSzfdDgtQD_udx?eHIe[xG[zHk|ghNg|Pdgve@@ePJeXTfPCf`MfhWgpOgxYiHZl`ek|gmPeLdhlTnmDwKxllHrl\nMlpm|gLtiMdjNToMtpNdvNmFOeDpQCO}EpMDPEEP]HPePQEOQKA?giEIC_?BDWnO{@?_kDqI_?CE_zL{@?gtFHt_OBEowN[@?W}Ghh_?AFxBM[C?h?GPx_OCH@NK{B?hHHhl_?@HPKNC??hQJHe_GAIXVLcB?`SIpq`?JHXKNsE@H@GP~_wIEwwOKE@PHHpm_wJFxCMcG@GlDqL_wHH@OLCE@?tFPu`OJDWoPCG@O}Gpi`GJE_{MCE?wiEQD_oJJ`bKsF@@\KHk`GIJp_MSMAHwNiD`_NNH{PCLA@yNYL`_OLhoPcLAHrMqJ`oNOA@PSL@xfLQP`_MM`tPsOAH~OQF`oOL@hQSNAHmLyN`_LNqBOcKAHeLYO`gML`pPKNA@qMyEa_VIpZOkQAhVJQGaWUJ@XPkQAoxFaPaWVFOzQSSAgwFiOaWTGXEPcQA`CGiNaoVGPFPKSApLIAJagVHpNPsQAXKIIEaOVKPbPSRA``KaFagUK@dOcYBgnEQPb?ZE?pQSXB_mEYOb?[IXZMCXBhSJPubOZIhXOKXBX?Gp|b?YFxFM{[Bh@GiBbO[HPONcZBhHIHpb?XHXNOSWBh^KXzbGYJhdL{ZB`]K`tc?bD_qPc]CGjEYHbwaDgpP{]COuF`|bwbEg|M{_CGvFYBbw`IPZLS]C@SJ@scObIhVN{_CPGIHjcGbHPMNS]BxJHi?bobJ`dLK^C@^KHxcGaJpaM[eDGiEYEc_fD_oP[dD?lDyMc_gE_|MKdDGuFP{cofEwxOSdCw}Gxjc_eG@CNSgDH@GY?cogIPYLCfDHRJ@mc_dIhUNscDH[K`fcgeJhaLkfD@^K@w") exoo212 = Graph(r":~?BS_C?_C?_C@_K@_KA_SA_SB_[B_[C_cC_cD_kD_kZBSMBSYbSYa_ZbGZb[ZbcUBc[bk\`W\bk]_o]bsLBsFB{^b{^e_r_wfE[r`Gra?rb?lEcqEcsect`wtbGu`Ou_ocEsuaov`g_E{eE{TCGwfCwbLHhKbHKPDHH`GNEHIh@I`PIapIbGgaOqH[MH[_FhJh[nHceFHKfpKdoyHlLeT[b@[`w{JciGH[cWgGx\jX\`p\dx\eP?dXGJsLCx]a`]gp^iP^aXDHx_``_hCTLkpLkgIHlgPTLkPF`?LtkLsfLtGIdBJXn`_eFxnaOlL|YMDdMCkJHaMKGChp`?mjX|gx}aX?K`}b@UNsiIHSNk~NlZK{VIxkN{dFpRN{HDX~mi?g`iMY@_waOKaGlkP[PPcTD`SPcpLAKgPcKyJ`XRP[oLH{PkFIPePkbGYLoaM`@WNQNcGzP{zJKLNaWdQXgxwRKTIpvRCcKqWa@xPQYcHdMqYf`VRSNCQGR[EFPOR\OLSePQbgQcaIFScmLAES[|MqbaWhQydfPtOidiHhSkgFYTSs_HxbSs}Q{VKXyTsEIqm`OiQamghwQYnhyCQQok`xUCxKPsUKSIQae@sPAu`pASAujIFRyv`_SKQ]hprOYwdhdTkOOYTVcfIqjVdiQaiVkdDhrTKGKIPVsH@XtUk~LAsWSJNQ_U[UCPqRjBaObCaCV[cPAjVSQDwzOQg`_jF_|WK|QisWCVDXEIAOe@BJPbRcOIxjMafdHhNYBUT@NIHQIxaXTQq\V{WDa`TBCawpGakW{IE@FJBI~~~") rajiv252nx = rajiv252.networkx_graph() exoo212nx =exoo212.networkx_graph() # List of graphs to process graphs = [('rajiv252 ', rajiv252),('exoo212 ', exoo212 )] 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("\n Main properties of the graph\n") for label, graph in graphs: print(f"{label} | Ord.: {graph.order()} / Size: {graph.size()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} / 5-reg.? {graph.is_regular(k=5)} / Girth: {graph.girth()} ")# / Alg.conn. {algebraic_connectivity(graph).n(digits=6)} / Domin. number: {domination_number(graph)} ") print("Degree histogram exoo212 :", nx.degree_histogram(exoo212nx)) print("\n Symmetry properties of the graph\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()}" ) print("\n") # automorphism group structure print(" Automorphism group structure: x means direct product; : means semidirect product.\n") Arajiv252 = rajiv252.automorphism_group() print('rajiv252 :', Arajiv252.structure_description(), ' | center order:',Arajiv252.center().order()) Aexoo212 = exoo212.automorphism_group() print('exoo212 :', Aexoo212.structure_description(), ' | center order:',Aexoo212.center().order()) print("\n") ''' print("\n Properties of the graphs as at arXiv\n") for label, graph in nonisographs: print(f"{label} & {graph.average_distance().n(digits=6)} & {graph.girth()} & {algebraic_connectivity(graph).n(digits=6)} & {graph.automorphism_group().order()} \\\\ ") ''' # 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 for label, graph in graphs: print(f"{label} distance distrib from vtx. 0: {distance_distribution(graph, 0)}") print(f"{label} distance distrib from vtx. 9: {distance_distribution(graph, 9)}") # Counting k-cycles for each graph print("\nNumber of k-cycles for k=3 up to 7") for label, graph in graphs: print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 8))) print("\n") ''' # from 0 versio Molodtsov for name, G in graphs: fname = name.strip() + "_adjlst.txt" s = "; ".join( "{}-{}".format(v, ",".join(map(str, G.neighbors(v)))) if G.neighbors(v) else str(v) for v in G.vertices(sort=True) ) with open(fname, "w") as f: f.write(s) # from 0 for label, _ in graphs: base = label.strip() G = globals()[base + "nx"] with open(f"{base}_edges.txt", "w") as f: f.write(",".join( f"{{{u},{v}}}" for u, v in sorted((min(u, v), max(u, v)) for u, v in G.edges()) )) ''' # from 1 for label, _ in graphs: base = label.strip() G = globals()[base + "nx"] with open(f"{base}_Zedges.txt", "w") as f: f.write(",".join( f"{{{u+1},{v+1}}}" for u, v in sorted((min(u, v), max(u, v)) for u, v in G.edges()) )) print("\n DONE \n") ##