# SageMathCell online -> https://sagecell.sagemath.org/?q=udvkcm # Dharunish Yugeswardeenoo (dharyugi@gmail.com; Sept. 14, 2026), graph with 106 nodes and 582 edges; Moore bound 122 # ''' Main properties of the graph dhar106 | Ord.: 106 / Size: 582 / Diam.: 2 / Avg.dist: 1.89542 / 11-reg.? False / Girth: 3 / Alg.conn. 6.66128 / Domin. number: 10.0 exoo104 | Ord.: 104 / Size: 572 / Diam.: 2 / Avg.dist: 1.89320 / 11-reg.? True / Girth: 3 / Alg.conn. 6.87689 / Domin. number: 10.0 Degree histogram dhar106 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 104] Degree histogram exoo104 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 104] Symmetry properties of the graph dhar106 | Aut.group.ord.: 56 / Cayley ? False --- vtx.trans. ? False -- edge.trans. ? False exoo104 | Aut.group.ord.: 84 / Cayley ? False --- vtx.trans. ? False -- edge.trans. ? False Automorphism group structure: x means direct product; : means semidirect product. dhar106 : C2 x C2 x D7 | center order: 4 exoo104 : C2 x (C7 : C6) | center order: 2 dhar106 distance distrib from vtx. 0: [1, 11, 94] dhar106 distance distrib from vtx. 9: [1, 11, 94] exoo104 distance distrib from vtx. 0: [1, 11, 92] exoo104 distance distrib from vtx. 9: [1, 11, 92] Number of k-cycles for k=3 up to 5 dhar106 53 446 12130 exoo104 84 449 11860 ''' import networkx as nx dhar106=Graph(r":~?@i__A??WA??WA?_GA?_GIDBGe@AOqJB?yFBGWK`?qIBG_K_oqDCWST`PYDDGCDCwSMCwSQ`PAGA`K]ao{WE`}BBOw^c`[^`os^GGCED`}HCPc^_`s^`@G[GGKQEaUHC`k]Gw_IB`GX_OkQGWKQEAUIB`SYEqq@@owPGgCAHai@@@?dHwCGDAKk`?scIAqEBp[`KgGMFQ?nKgkSDPceIQwqKw[OEqGqa?gPFAkqaO{]IbIADqKjJRaED`cZGB]BCP[_IbYCCpobIb?r`?wODqWpMg[QE@gcIbuJBPk`Ig?BD@SaLBqAEpsdKrO}a?wSE@kgMXCZHa[wOGkUFAGpMCECCP_YGQcnPGWLHasoMsHCa?gNFRXD_p?\GqWnLsEHCpspLRmHBpwhLrx?PgGWEaGoLr|H`_wUEQKcOs\Jaos`IrxBQWKRFA[oLRc}Pw_OEaorOwgOEA_pKsMECPwpLB|Ma?gLHqx@aPWWEaWjLbpPSgONEQGlOc`LSWcSDP[cHr|FQG[REQksPCXNSDUFD`wfJQ{rOcdJ_o{]IR_|QtHU`@W\GAwxNshNSGWOEQOxMc@DQTIED@S[HQ{uMStWUWkLHQk|Ns@FTw[NFAWgJB|YaOsaJrhMRt@\`@OTFakzOSp\Vg_ID`[hKBPLVWG[HAczRt@QTDqFD@S\GR?wMdP`_`wgJAwyNCXFRTUECp_YJb`GVD|__`c`HrCuQe@capKVIAonQcpQSuIJCPscJRpAUDxd_OgTGq_|PCdNSUUFB@[dJb[zOsTPX~") exoo104=Graph(r":~?@g_GA?_G?@_GA?_GA?_Oe@AwCI_O]@?gCD_OQ@@gCG__qACgGL_`MABwGMDGGP_`AAC@mBCPqBCPs]_p?ZFGKLEgKKDgKNEGKSEWKQDwKRDWKMEWORFQOf`?wSFAICB@__`?{VHgOOGWOLEqMCCPSd`@GYFaUCC`c^JgSVGqeDDQCg`PWfJGSYHaiDDaOkKwSWHQwnKGSZF@s_IwSXGauEBPScHq{v`_wSFQSiMGWQFAKkKgWODqGjLgWNEa?mKrUEB@k`IB?p``CXHacs``KUFaWlLGWRDp{kLB}FB`OVGB?qOG[REqShKrUFB@ocHqsuOW[LEPsaJbOz`p?UHa{wNg[QEACiLr}FBpS]GqopMg[PEaKgKRqFBpW^IbCxQW_ICpo`Jb`AQg_ICAKhKBOxOw_IBPW_IBW~QG_IC`g\HbC|PG_IB@cdJB\?QW_IBpkaJrGyOW_ICP[cHqgzPg_ME@wjLRxDa?wTFqOlKrpFaOwSDaKmLsDERWcNDPs`IRX?OtEHCpc_JrCzPTMHC`kcHqksNC`JaP?dJRG~PChQaOs[HagoKrSyQTAHB@[]Ga_wNS\KaOoYFqkwMsLLaPCWGaowMSHMUwgSDP{fJRS{PtYID@_]IrK}PTHWaooVFQKnKrS~OcmJB`OZHaouMshNUgkQDQ?wMSDHSdT]ap?WHA[mKS@FSDmJBpodIBO}PdL[VWkREaGlKB[|QDDWapCUGQkqMcPKTgkLEPw`IbG{OsxSaosWFqcqNSXNTuV") dhar106nx = dhar106.networkx_graph() exoo104nx = exoo104.networkx_graph() # List of graphs to process graphs = [('dhar106 ',dhar106),('exoo104 ', exoo104 )] 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)} / 11-reg.? {graph.is_regular(k=11)} / Girth: {graph.girth()} / Alg.conn. {algebraic_connectivity(graph).n(digits=6)} / Domin. number: {domination_number(graph)} ") print("Degree histogram exoo104 :", nx.degree_histogram(exoo104nx)) print("Degree histogram dhar106 :", nx.degree_histogram(dhar106nx)) 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") Adhar106 = dhar106.automorphism_group() print('dhar106 :', Adhar106.structure_description(), ' | center order:',Adhar106.center().order()) Aexoo104 = exoo104.automorphism_group() print('exoo104 :', Aexoo104.structure_description(), ' | center order:',Aexoo104.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 5") for label, graph in graphs: print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 6))) 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") ##