Ask Your Question
0

Reference for cospectral_graphs function?

asked 2024-04-01 02:38:21 +0200

Adjason gravatar image

What is the reference for the cospectral_graphs function in sage math? I don’t see it in the documentation.

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2024-04-01 12:49:36 +0200

rburing gravatar image

updated 2024-04-01 12:57:56 +0200

The cospectral_graphs function was added in #9141. Credits:

  • Jason Grout (2010-06-04): cospectral_graphs

The implementation is quite straightforward. First the optional matrix_function argument is read:

if matrix_function is None:
    matrix_function = lambda g: g.adjacency_matrix()

Then the optional graphs argument is read:

from sage.graphs.graph_generators import graphs as graph_gen
if graphs is None:
    graph_list = graph_gen(vertices, property=lambda _: True)
elif callable(graphs):
    graph_list = iter(g for g in graph_gen(vertices, property=lambda _: True) if graphs(g))
else:
    graph_list = iter(graphs)

Finally the cospectral graphs are generated, by putting each graph in a bucket labeled by the graph's characteristic polynomial:

from collections import defaultdict
charpolys = defaultdict(list)
for g in graph_list:
    cp = matrix_function(g).charpoly()
    charpolys[cp].append(g)

... and then taking the contents of those buckets containing more than one graph:

cospectral_graphs = []
for cp, g_list in charpolys.items():
    if len(g_list) > 1:
        cospectral_graphs.append(g_list)

return cospectral_graphs
edit flag offensive delete link more

Comments

Thank you for explaining!

Adjason gravatar imageAdjason ( 2024-04-02 01:54:44 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2024-03-31 22:11:03 +0200

Seen: 82 times

Last updated: Apr 01