I have not tested it on 10-vertex, 11-edge graphs, and its correctness has not been verified on a large number of examples.
good_graphs = []
for g in graphs.nauty_geng("5 6 -c"): # 5-vertex 6 edges
if spectra_diff_one_edge(g):
good_graphs.append(g)
key function
from collections import Counter
def one_value_change(list1, list2, tol=1e-6):
"""
Check if two lists differ by exactly one value (considering multiplicity and tolerance).
Parameters:
list1, list2 : lists of numbers
tol : float, two numbers within tol are considered equal
Returns:
(bool, old_value, new_value) :
- True and the changed values if exactly one element differs
- False, None, None otherwise
"""
def multiset(seq):
# Round each number to tol precision
return Counter(round(x / tol) * tol for x in seq)
c1 = multiset(list1)
c2 = multiset(list2)
diff1 = c1 - c2
diff2 = c2 - c1
if len(diff1) == 1 and len(diff2) == 1:
old_val = list(diff1.elements())[0]
new_val = list(diff2.elements())[0]
return True, old_val, new_val
else:
return False, None, None
def spectra_diff_one_edge(g, return_info=False, tol=1e-6):
"""
Check if there exists an edge that can be added to graph g such that
the Laplacian spectrum changes in exactly one eigenvalue.
Parameters:
g (Graph): a Sage graph
return_info (bool):
- If True, return (u, v, old_val, new_val) for the edge that
changes exactly one eigenvalue.
- If False, return True/False indicating whether such an edge exists.
tol (float): tolerance for eigenvalue comparison
Returns:
If return_info=False:
bool: True if such an edge exists, otherwise False
If return_info=True:
tuple or None: (u, v, old_val, new_val) if an edge exists that changes
exactly one eigenvalue, otherwise None
"""
base_spec = [RR(x) for x in g.laplacian_matrix().eigenvalues()]
comp = g.complement()
for (u, v) in comp.edges(labels=False):
g.add_edge(u, v)
new_spec = [RR(x) for x in g.laplacian_matrix().eigenvalues()]
g.delete_edge(u, v)
changed, old_val, new_val = one_value_change(base_spec, new_spec, tol)
if changed:
if return_info:
return (u, v, old_val, new_val)
else:
return True
return False if not return_info else None
For exmaple, I will get two graphs by running the above codes.
g=good_graphs[0]
g.show()
g.laplacian_matrix().eigenvalues()

[5, 4, 2, 1, 0]
spectra_diff_one_edge(g, return_info=True, tol=1e-6)
It gives (0, 1, 2.00000000000000, 4.00000000000000)
which means that add the edge (0,1) will change only one eigenvalue.
g.add_edge(0, 1)
print(g.laplacian_matrix().eigenvalues())
[5, 1, 0, 4, 4]
We compare the symmetric difference of the two lists, and only the values 2 and 4 are different, while all the others match. (Here, note that I’m a bit unsure about your exact meaning of a position change—my understanding is that only two values are different.)
What is the question?
@max Alekseyev I think the OP wants to select graphs from the above collection such that adding some edge (existence suffices, not a specific one) changes exactly one Laplacian eigenvalue.
Still, what is the question? This is a Q&A website.
@licheng, yes you are correct.
@Max Alekseyev, the main question is to investigate those graphs having the above mentioned property. And to do that I want to find some examples. So this is the main question.