# SageMathCell online # https://sagecell.sagemath.org/?q=xjxyjk # 13 non-isomorphic graphs found by James Allwrigth. # The variable G is the graph in sparse6 format . G1a=Graph(r":h_OoCMFCaPGOUJD_PpK_T?@rx{s`O`AACcbP_raKWeTddAsWpJHEwxYSRMqaP]KUNqqX]AALfWx`B@FEh_sqceFBsGW_PqAh\L") #1a G1b=Graph(r":h_OoCMFCaPGOUJD_PpK_T?@rx{s`O`AACcbP_raKWeTddAsWdJKEwxYSRMqaP]KUNqqX]AALfWx`B@FEh_sqceFBsGW_PqAh\L") #1b G1c=Graph(r":h_OoCMFCaPGOUJD_PpK_T?@rx{s`O`AACcbP_raKWeTddAsWdJKEwxYSRMqaP]KUNqqX]AALfWx`B@FEX_ssceFBsGW_PqAh\LL") #1c G1d=Graph(r":h_OoCMFCaPGOUJD_Px?i?BfrxhA`ACCHGsbP_raKWQRddAsWdJKEwxYSRMqaP]KUNqqX]AALfWx`B@FEX_ssceFBsGW_PqAh\L") #1d G1e=Graph(r":h_OoCMFCaPGOUJD_PxS?FNfrQDACGFCHGsbP_raKWQRcAqsWdJKEwxYSRMqaP]KUNqqX]AALfWx`B@FEX_ssceFBsGW_PqAh\L") #1e G1f=Graph(r":h_OoCMFCaPGOUJD_PxS?FNfrQDACGFCHGsbP_raKWQRcAqskdEKEwxYSRMqaP]KUNqqX]AALfWx`B@FEX_ssceFBsGW_PqAh\L") #1f G2a=Graph(r":h_OoCMFCaPGOSPDaoGoiMJ_?x{}`OecGOwaSgoYK_cUccrCgmWbDhXIMQLqqX[xEKFXPYAAMpqYDD@EeX_wsceGCKGW[NQA`\L") #2a G2b=Graph(r":h_OoCMFCaPGOSPDaoGoiMJ_?x{}`OecGOwaSgoYK_cUccrCgmWbDhXIMQLqqX[xEKFXPYAAOPqYDD@EeX_wsceFSKGW[NQA`\L") #2b G2c=Graph(r":h_OoCMFCaPGOSPDaoGoiMJ_?x{}`OecGOwaSgoYKccUcCrCgmWbDhXIMQLqqX[xEKFXPYAAOPqYDD@EeX_wsceFSKGW[NQA`\L") #2c G3=Graph(r":h_P?K?FG@PX_CVA@oxLCMKbAaDOOMj?@C{aSbaQ@YGDhEX@St?DBgXCeY`@?{g]RNO`Ww`ECbWo[i[dBBYEAOJp?pQURJHXhKicdbqhf") #G3 G4=Graph(r":h_OWSMBD`@g{KP?cAgomGK`agCO^@Erhg{dIGSQc[eSachHSnDGQP{yaZbEb[_q[eEJHk~QNTRiEs[dds\X?b_FsKHIeaGca^") #G4 G5=Graph(r":h_OWS?FCao?sIKG`PPS_V@EPpkc\BFpaDESQdBx`EHSIdiPYeUiTRSCcYceWXkzMKFhX}__eeSKSsacEC[[eZmFSC?meohCi^") #G5 G6=Graph(r":h`?W_MACaq?G]?GbP_{YCB`Og?QQIdoyHGf@IQpsg^HETaxaGTKo@_}iZjFHx?dKFCxOsz]NgH@hB?@`rkw_PecbC[eVqHSsSwaR~") #G6 # List of graphs to process graphs = [ ('Graph 1(a)', G1a), ('Graph 1(b)', G1b), ('Graph 1(c)', G1c), ('Graph 1(d)', G1d), ('Graph 1(e)', G1e), ('Graph 1(f)', G1f), ('Graph 2(a)', G2a), ('Graph 2(b)', G2b), ('Graph 2(c)', G2c), ('Graph 3 ', G3),('Graph 4 ', G4),('Graph 5 ', G5), ('Graph 6 ', G6)] def check_all_isomorphisms(graph_list): n = len(graph_list) print("\n Isomorphism 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("\n Main properties of the graphs\n") for label, graph in graphs: print(f"{label} | Order: {graph.order()} / Size: {graph.size()} / 4-reg.? {graph.is_regular(k=4)} " f" / Girth: {graph.girth()} / Diam.: {graph.diameter()} / Avg.dist: {graph.average_distance().n(digits=6)} / Alg.connect. {algebraic_connectivity(graph).n(digits=6)} Domin. number: {domination_number(graph)}" f" / Aut.group.order: {graph.automorphism_group().order()}") # 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("\n") 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 10") for label, graph in graphs: print(f"{label} ", " ".join(str(count_k_cycles(graph, k)) for k in range(3, 11))) ## """ RESULTS Main properties of the graphs Graph 1(a) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 9.0 / Aut.group.order: 2 Graph 1(b) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 9.0 / Aut.group.order: 2 Graph 1(c) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 9.0 / Aut.group.order: 2 Graph 1(d) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 9.0 / Aut.group.order: 1 Graph 1(e) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 9.0 / Aut.group.order: 2 Graph 1(f) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 9.0 / Aut.group.order: 4 Graph 2(a) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 10.0 / Aut.group.order: 2 Graph 2(b) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 10.0 / Aut.group.order: 6 Graph 2(c) | Order: 41 / Size: 82 / 4-reg.? True / Girth: 3 / Diam.: 3 / Avg.dist: 2.50366 / Alg.connect. 1.42578 Domin. number: 10.0 / Aut.group.order: 6 Graph 3 | Order: 41 / Size: 82 / 4-reg.? True / Girth: 5 / Diam.: 3 / Avg.dist: 2.50000 / Alg.connect. 1.45566 Domin. number: 10.0 / Aut.group.order: 1 Graph 4 | Order: 41 / Size: 82 / 4-reg.? True / Girth: 5 / Diam.: 3 / Avg.dist: 2.50000 / Alg.connect. 1.42753 Domin. number: 10.0 / Aut.group.order: 2 Graph 5 | Order: 41 / Size: 82 / 4-reg.? True / Girth: 5 / Diam.: 3 / Avg.dist: 2.50000 / Alg.connect. 1.44828 Domin. number: 10.0 / Aut.group.order: 2 Graph 6 | Order: 41 / Size: 82 / 4-reg.? True / Girth: 5 / Diam.: 3 / Avg.dist: 2.50000 / Alg.connect. 1.34891 Domin. number: 10.0 / Aut.group.order: 12 Isomorphism check of all pairs (a dot means non isomorphic): .............................................................................. Graph 1(a) distance distrib: [1, 4, 10, 26] Graph 1(b) distance distrib: [1, 4, 10, 26] Graph 1(c) distance distrib: [1, 4, 10, 26] Graph 1(d) distance distrib: [1, 4, 10, 26] Graph 1(e) distance distrib: [1, 4, 10, 26] Graph 1(f) distance distrib: [1, 4, 10, 26] Graph 2(a) distance distrib: [1, 4, 10, 26] Graph 2(b) distance distrib: [1, 4, 10, 26] Graph 2(c) distance distrib: [1, 4, 10, 26] Graph 3 distance distrib: [1, 4, 12, 24] Graph 4 distance distrib: [1, 4, 12, 24] Graph 5 distance distrib: [1, 4, 12, 24] Graph 6 distance distrib: [1, 4, 12, 24] Number of k-cycles for k=3 up to 10 Graph 1(a) 1 0 3 83 284 495 922 2639 Graph 1(b) 1 0 5 77 288 491 928 2686 Graph 1(c) 1 0 3 81 290 493 918 2639 Graph 1(d) 1 0 3 79 296 491 906 2667 Graph 1(e) 1 0 3 81 290 493 918 2635 Graph 1(f) 1 0 1 83 298 485 924 2632 Graph 2(a) 1 0 3 81 288 493 926 2645 Graph 2(b) 1 0 3 77 300 489 902 2709 Graph 2(c) 1 0 3 75 306 483 904 2751 Graph 3 0 0 15 63 275 521 958 2752 Graph 4 0 0 15 63 275 521 954 2770 Graph 5 0 0 15 63 275 517 974 2743 Graph 6 0 0 15 67 267 525 937 2745 """