def barrus_bound(g):
"""
returns n - barrus q
defined in: Barrus, Michael D. "Havel–Hakimi residues of unigraphs." Information Processing Letters 112.1 (2012): 44-48.
sage: barrus_bound(k4):
1
2
"""
return g.order() - barrus_q(g)
def distinct_degrees(g):
"""
returns the number of distinct degrees of a graph
sage: distinct_degrees(p4)
2
sage: distinct_degrees(k4)
1
"""
return len(set(g.degree()))
def common_neighbors(g,v,w):
"""
returns the Set of common neighbors of v and w in graph g
sage: common_neighbors(p4,0,3)
{}
sage: common_neighbors(p4,0,2)
{1}
"""
Nv = Set(g.neighbors(v))
Nw = Set(g.neighbors(w))
return Nv.intersection(Nw)
def max_common_neighbors(g):
"""
returns the maximum number of common neighbors of any pair of distinct vertices in g
sage: max_common_neighbors(p4)
1
sage: max_common_neighbors(k4)
2
"""
max = 0
V = g.vertices()
n = g.order()
for i in range(n):
for j in range(n):
if i < j:
temp = len(common_neighbors(g, V[i], V[j]))
if temp > max:
max = temp
return max
def min_common_neighbors(g):
"""
returns the minimum number of common neighbors of any pair of distinct vertices in g,
which is necessarily 0 for disconnected graphs
sage: min_common_neighbors(p4)
0
sage: min_common_neighbors(k4)
2
"""
n = g.order()
min = n
V = g.vertices()
for i in range(n):
for j in range(n):
if i < j:
temp = len(common_neighbors(g, V[i], V[j]))
if temp < min:
min = temp
return min
def mean_common_neighbors(g):
"""
returns the average number of common neighbors of any pair of distinct vertices in g
sage: mean_common_neighbors(p4)
1/3
sage: mean_common_neighbors(k4)
2
"""
V = g.vertices()
n = g.order()
sum = 0
for i in range(n):
for j in range(n):
if i < j:
sum += len(common_neighbors(g, V[i], V[j]))
return 2*sum/(n*(n-1))
def domination_number(g):
"""
Returns the domination number of the graph g, i.e., the size of a maximum
dominating set.
A complete graph is dominated by any of its vertices::
sage: domination_number(graphs.CompleteGraph(5))
1
A star graph is dominated by its central vertex::
sage: domination_number(graphs.StarGraph(5))
1
The domination number of a cycle of length n is the ceil of n/3.
sage: domination_number(graphs.CycleGraph(5))
2
"""
return g.dominating_set(value_only=True)
def min_degree(g):
"""
Returns the minimum of all degrees of the graph g.
sage: min_degree(graphs.CompleteGraph(5))
4
sage: min_degree(graphs.CycleGraph(5))
2
sage: min_degree(graphs.StarGraph(5))
1
sage: min_degree(graphs.CompleteBipartiteGraph(3,5))
3
"""
return min(g.degree())
def max_degree(g):
"""
Returns the maximum of all degrees of the graph g.
sage: max_degree(graphs.CompleteGraph(5))
4
sage: max_degree(graphs.CycleGraph(5))
2
sage: max_degree(graphs.StarGraph(5))
5
sage: max_degree(graphs.CompleteBipartiteGraph(3,5))
5
"""
return max(g.degree())
def eulerian_faces(g):
"""
Returns 2 - order + size, which is the number of faces if the graph is planar,
a consequence of Euler's Formula
sage: eulerian_faces(graphs.CycleGraph(5))
2
sage: eulerian_faces(graphs.DodecahedralGraph())
12
"""
n = g.order()
m = g.size()
return 2 - n + m
def barrus_q(g):
"""
If the degrees sequence is in non-increasing order, with index starting at 1,
barrus_q = max(k:d_k >= k)
Defined by M. Barrus in "Havel-Hakimi Residues of Unigraphs", 2012
sage: barrus_q(graphs.CompleteGraph(5))
4
sage: barrus_q(graphs.StarGraph(3))
1
"""
Degrees = g.degree()
Degrees.sort()
Degrees.reverse()
return max(k for k in range(g.order()) if Degrees[k] >= (k+1)) + 1
def matching_number(g):
"""
Returns the matching number of the graph g, i.e., the size of a maximum
matching. A matching is a set of independent edges.
sage: matching_number(graphs.CompleteGraph(5))
2
sage: matching_number(graphs.CycleGraph(5))
2
sage: matching_number(graphs.StarGraph(5))
1
sage: matching_number(graphs.CompleteBipartiteGraph(3,5))
3
"""
return int(g.matching(value_only=True, use_edge_labels=False))
def residue(g):
seq = g.degree_sequence()
while seq[0] > 0:
d = seq.pop(0)
seq[:d] = [k-1 for k in seq[:d]]
seq.sort(reverse=True)
return len(seq)
def annihilation_number(g):
seq = sorted(g.degree())
a = 0
while sum(seq[:a+1]) <= sum(seq[a+1:]):
a += 1
return a
def fractional_alpha(g):
if len(g.vertices()) == 0:
return 0
p = MixedIntegerLinearProgram(maximization=True)
x = p.new_variable(nonnegative=True)
p.set_objective(sum(x[v] for v in g.vertices()))
for v in g.vertices():
p.add_constraint(x[v], max=1)
for (u,v) in g.edge_iterator(labels=False):
p.add_constraint(x[u] + x[v], max=1)
return p.solve()
def fractional_covering(g):
if len(g.vertices()) == 0:
return 0
p = MixedIntegerLinearProgram(maximization=False)
x = p.new_variable(nonnegative=True)
p.set_objective(sum(x[v] for v in g.vertices()))
for v in g.vertices():
p.add_constraint(x[v], min=1)
for (u,v) in g.edge_iterator(labels=False):
p.add_constraint(x[u] + x[v], min=1)
return p.solve()
def cvetkovic(g):
eigenvalues = g.spectrum()
positive = 0
negative = 0
zero = 0
for e in eigenvalues:
if e > 0:
positive += 1
elif e < 0:
negative += 1
else:
zero += 1
return zero + min([positive, negative])
def cycle_space_dimension(g):
return g.size()-g.order()+g.connected_components_number()
def card_center(g):
return len(g.center())
def cycle_space_dimension(g):
return g.size()-g.order()+g.connected_components_number()
def card_periphery(g):
return len(g.periphery())
def max_eigenvalue(g):
return max(g.adjacency_matrix().change_ring(RDF).eigenvalues())
def resistance_distance_matrix(g):
L = g.laplacian_matrix()
n = g.order()
J = ones_matrix(n,n)
temp = L+(1.0/n)*J
X = temp.inverse()
R = (1.0)*ones_matrix(n,n)
for i in range(n):
for j in range(n):
R[i,j] = X[i,i] + X[j,j] - 2*X[i,j]
return R
def kirchhoff_index(g):
R = resistance_distance_matrix(g)
return .5*sum(sum(R))
def largest_singular_value(g):
A = matrix(RDF,g.adjacency_matrix())
svd = A.SVD()
sigma = svd[1]
return sigma[0,0]
def independence_number(g):
return g.independent_set(value_only=True)
def chromatic_index(g):
if g.size() == 0:
return 0
import sage.graphs.graph_coloring
return sage.graphs.graph_coloring.edge_coloring(g, value_only=True)
def chromatic_num(g):
return g.chromatic_number()
def card_max_cut(g):
return g.max_cut(value_only=True)
def clique_covering_number(g):
if g.is_triangle_free():
return g.order() - matching_number(g)
gc = g.complement()
return gc.chromatic_number(algorithm="MILP")
def welsh_powell(g):
n= g.order()
D = g.degree()
D.sort(reverse=True)
mx = 0
for i in range(n):
temp = min({i,D[i]})
if temp > mx:
mx = temp
return mx + 1
def brooks(g):
Delta = max(g.degree())
delta = min(g.degree())
n = g.order()
if is_complete(g):
return Delta + 1
elif n%2 == 1 and g.is_connected() and Delta == 2 and delta == 2:
return Delta + 1
else:
return Delta
def wilf(g):
return max_eigenvalue(g) + 1
def n_over_alpha(g):
n = g.order() + 0.0
return n/independence_number(g)
def median_degree(g):
return median(g.degree())
def different_degrees(g):
return len(set(g.degree()))
def szekeres_wilf(g):
def remove_vertex_of_degree(gc,i):
Dc = gc.degree()
V = gc.vertices()
mind = min(Dc)
if mind <= i:
ind = Dc.index(mind)
return gc.delete_vertex(V[ind])
else:
return gc
D = g.degree()
delta = min(D)
Delta = max(D)
for i in range(delta,Delta+1):
gc = copy(g)
value = g.order() + 1
while gc.size() > 0 and gc.order() < value:
value = gc.order()
remove_vertex_of_degree(gc,i)
if gc.size() == 0:
return i + 1
def average_vertex_temperature(g):
D = g.degree()
n = g.order()
return sum([D[i]/(n-D[i]+0.0) for i in range(n)])/n
def sum_temperatures(g):
D = g.degree()
n = g.order()
return sum([D[i]/(n-D[i]+0.0) for i in range(n)])
def randic(g):
D = g.degree()
V = g.vertices()
if min(D) == 0:
return oo
sum = 0
for e in g.edges():
v = e[0]
i = V.index(v)
w = e[1]
j = V.index(w)
sum += 1.0/(D[i]*D[j])**0.5
return sum
def bipartite_chromatic(g):
if g.is_bipartite():
return 2
else:
return g.order()
def max_even_minus_even_horizontal(g):
"""
finds def max_even_minus_even_horizontal for each component and adds them up.
"""
mx_even=0
Gcomps=g.connected_components_subgraphs()
while Gcomps != []:
H=Gcomps.pop()
temp=max_even_minus_even_horizontal_component(H)
mx_even+=temp
return mx_even
def max_even_minus_even_horizontal_component(g):
"""
for each vertex v, find the number of vertices at even distance from v,
and substract the number of edges induced by these vertices.
this number is a lower bound for independence number.
take the max. returns 0 if graph is not connected
"""
if g.is_connected()==False:
return 0
distances = g.distance_all_pairs()
mx=0
n=g.order()
for v in g.vertices():
Even=[]
for w in g.vertices():
if distances[v][w]%2==0:
Even.append(w)
l=len(Even)-len(g.subgraph(Even).edges())
if l>mx:
mx=l
return mx
def median_degree(g):
return median(g.degree())
def laplacian_energy(g):
L = g.laplacian_matrix().change_ring(RDF).eigenvalues()
Ls = [1/lam**2 for lam in L if lam > 0]
return 1 + sum(Ls)
def gutman_energy(g):
L = g.adjacency_matrix().change_ring(RDF).eigenvalues()
Ls = [lam for lam in L if lam > 0]
return sum(Ls)
def fiedler(g):
L = g.laplacian_matrix().change_ring(RDF).eigenvalues()
L.sort()
return L[1]
def average_degree(g):
return mean(g.degree())
def degree_variance(g):
mu = mean(g.degree())
s = sum((x-mu)**2 for x in g.degree())
return s/g.order()
def number_of_triangles(g):
E = g.edges()
D = g.distance_all_pairs()
total = 0
for e in E:
v = e[0]
w = e[1]
S = [u for u in g.vertices() if D[u][v] == 1 and D[u][w] == 1]
total += len(S)
return total/3
def graph_rank(g):
return g.adjacency_matrix().rank()
def inverse_degree(g):
return sum([(1.0/d) for d in g.degree() if d!= 0])
def card_positive_eigenvalues(g):
return len([lam for lam in g.adjacency_matrix().eigenvalues() if lam > 0])
def card_zero_eigenvalues(g):
return len([lam for lam in g.adjacency_matrix().eigenvalues() if lam == 0])
def card_negative_eigenvalues(g):
return len([lam for lam in g.adjacency_matrix().eigenvalues() if lam < 0])
def card_cut_vertices(g):
return len((g.blocks_and_cut_vertices())[1])
def independent_dominating_set_number(g):
return g.dominating_set(value_only=True, independent=True)
def average_distance(g):
if not g.is_connected():
return Infinity
V = g.vertices()
D = g.distance_all_pairs()
n = g.order()
return sum([D[v][w] for v in V for w in V if v != w])/(n*(n-1))
def card_pendants(g):
return sum([x for x in g.degree() if x == 1])
def vertex_con(g):
return g.vertex_connectivity()
def edge_con(g):
return g.edge_connectivity()
def card_bridges(g):
gs = g.strong_orientation()
bridges = []
for scc in gs.strongly_connected_components():
bridges.extend(gs.edge_boundary(scc))
return len(bridges)
def alon_spencer(g):
delta = min(g.degree())
n = g.order()
return n*((1+log(delta + 1.0)/(delta + 1)))
def caro_wei(g):
return sum([1.0/(d + 1) for d in g.degree()])
def degree_sum(g):
return sum(g.degree())
def sigma_2(g):
if g.size() == g.order()*(g.order()-1)/2:
return g.order()
Dist = g.distance_all_pairs()
return min(g.degree(v) + g.degree(w) for v in g for w in g if Dist[v][w] > 1)
def order_automorphism_group(g):
return g.automorphism_group(return_group=False, order=True)
def brinkmann_steffen(g):
E = g.edges()
if len(E) == 0:
return 0
Dist = g.distance_all_pairs()
return min(g.degree(v) + g.degree(w) for v in g for w in g if Dist[v][w] == 1)
def order_automorphism_group(g):
return g.automorphism_group(return_group=False, order=True)
def alpha_critical_optimum(g, alpha_critical_names):
n = g.order()
V = g.vertices()
alpha_critical_graph_names = []
for name in alpha_critical_names:
h = Graph(name)
if h.order() <= n:
alpha_critical_graph_names.append(h.graph6_string())
LP = MixedIntegerLinearProgram(maximization=True)
b = LP.new_variable(nonnegative=True)
LP.set_objective(sum([b[v] for v in g]))
for (u,v) in g.edges(labels=None):
LP.add_constraint(b[u]+b[v],max=1)
i = 3
while i <= n:
SS = Subsets(Set(V),i)
for S in SS:
L = [g6 for g6 in alpha_critical_graph_names if Graph(g6).order() == i]
for g6 in L:
h = Graph(g6)
if g.subgraph(S).subgraph_search(h, induced=False):
alpha = independence_number(h)
LP.add_constraint(sum([b[j] for j in S]), max = alpha, name = h.graph6_string())
i = i + 1
LP.solve()
b_sol = LP.get_values(b)
return b_sol, sum(b_sol.values())
def find_stable_ones_vertices(g):
F = []
alpha_f = fractional_alpha(g)
for v in g.vertices():
gc = copy(g)
gc.delete_vertices(closed_neighborhood(gc, v))
alpha_f_prime = fractional_alpha(gc)
if abs(alpha_f - alpha_f_prime - 1) < .01:
F.append(v)
return F
def find_max_critical_independent_set(g):
S = find_stable_ones_vertices(g)
H = g.subgraph(S)
return H.independent_set()
def critical_independence_number(g):
return len(find_max_critical_independent_set(g))
def card_independence_irreducible_part(g):
return len(find_independence_irreducible_part(g))
def find_independence_irreducible_part(g):
X = find_KE_part(g)
SX = Set(X)
Vertices = Set(g.vertices())
return list(Vertices.difference(SX))
def find_KE_part(g):
return closed_neighborhood(g, find_max_critical_independent_set(g))
def card_KE_part(g):
return len(find_KE_part(g))
def find_independence_irreducible_subgraph(g):
return g.subgraph(find_independence_irreducible_part(g))
def find_KE_subgraph(g):
return g.subgraph(find_KE_part(g))
def make_invariant_from_property(property, name=None):
"""
This function takes a property as an argument and returns an invariant
whose value is 1 if the object has the property, else 0
Optionally a name for the new property can be provided as a second argument.
"""
def boolean_valued_invariant(g):
if property(g):
return 1
else:
return 0
if name is not None:
boolean_valued_invariant.__name__ = name
elif hasattr(property, '__name__'):
boolean_valued_invariant.__name__ = '{}_value'.format(property.__name__)
else:
raise ValueError('Please provide a name for the new function')
return boolean_valued_invariant
efficiently_computable_invariants = [average_distance, Graph.diameter, Graph.radius,
Graph.girth, Graph.order, Graph.size, Graph.szeged_index, Graph.wiener_index,
min_degree, max_degree, matching_number, residue, annihilation_number, fractional_alpha,
Graph.lovasz_theta, cvetkovic, cycle_space_dimension, card_center, card_periphery,
max_eigenvalue, kirchhoff_index, largest_singular_value, vertex_con, edge_con,
Graph.maximum_average_degree, Graph.density, welsh_powell, wilf, brooks,
different_degrees, szekeres_wilf, average_vertex_temperature, randic, median_degree,
max_even_minus_even_horizontal, fiedler, laplacian_energy, gutman_energy, average_degree,
degree_variance, number_of_triangles, graph_rank, inverse_degree, sum_temperatures,
card_positive_eigenvalues, card_negative_eigenvalues, card_zero_eigenvalues,
card_cut_vertices, Graph.clustering_average, Graph.connected_components_number,
Graph.spanning_trees_count, card_pendants, card_bridges, alon_spencer, caro_wei,
degree_sum, order_automorphism_group, sigma_2, brinkmann_steffen,
card_independence_irreducible_part, critical_independence_number, card_KE_part,
fractional_covering, eulerian_faces, barrus_q, mean_common_neighbors,
max_common_neighbors, min_common_neighbors, distinct_degrees, barrus_bound]
intractable_invariants = [independence_number, domination_number, chromatic_index,
Graph.clique_number, clique_covering_number, n_over_alpha, chromatic_num,
independent_dominating_set_number]
invariants = efficiently_computable_invariants + intractable_invariants
def has_star_center(g):
"""
tests if graph has vertex adjacent to all others
sage: has_star_center(flower_with_3_petals)
True
sage: has_star_center(c4)
False
"""
n = g.order()
return max_degree(g) == (n-1)
def is_complement_of_chordal(g):
"""
tests is a graph is a complement of a chordal graph
sage: is_complement_of_chordal(p4)
True
sage: is_complement_of_chordal(p5)
False
"""
h = g.complement()
return h.is_chordal()
def pairs_have_unique_common_neighbor(g):
"""
tests if a graph is a collection of disjoint triangles with a single identified vertex
sage: pairs_have_unique_common_neighbor(flower(5))
True
sage: pairs_have_unique_common_neighbor(k3)
True
sage: pairs_have_unique_common_neighbor(k4)
False
"""
if max_common_neighbors(g) != 1:
return False
elif min_common_neighbors(g) != 1:
return False
else:
return True
def is_dirac(g):
n = g.order()
deg = g.degree()
delta=min(deg)
if n/2 <= delta and n > 2:
return True
else:
return False
def is_ore(g):
A = g.adjacency_matrix()
n = g.order()
D = g.degree()
for i in range(n):
for j in range(i):
if A[i][j]==0:
if D[i] + D[j] < n:
return False
return True
def is_haggkvist_nicoghossian(g):
k = vertex_con(g)
n = g.order()
delta = min(g.degree())
if k >= 2 and delta >= (1.0/3)*(n+k):
return True
else:
return False
def is_fan(g):
k = vertex_con(g)
if k < 2:
return False
D = g.degree()
Dist = g.distance_all_pairs()
V = g.vertices()
n = g.order()
for i in range(n):
for j in range (i):
if Dist[V[i]][V[j]]==2 and max(D[i],D[j]) < n/2.0:
return False
return True
def is_planar_transitive(g):
if g.order() > 2 and g.is_planar() and g.is_vertex_transitive():
return True
else:
return False
def neighbors_set(g,S):
N = set()
for v in S:
for n in g.neighbors(v):
N.add(n)
return list(N)
def is_generalized_dirac(g):
n = g.order()
k = vertex_con(g)
if k < 2:
return False
for p in Subsets(g.vertices(),2):
if g.is_independent_set(p):
if len(neighbors_set(g,p)) < (2.0*n-1)/3:
return False
return True
def is_van_den_heuvel(g):
n = g.order()
lc = sorted(graphs.CycleGraph(n).laplacian_matrix().eigenvalues())
lg = sorted(g.laplacian_matrix().eigenvalues())
for lci, lgi in zip(lc, lg):
if lci > lgi:
return False
def Q(g):
A = g.adjacency_matrix()
D = A.parent(0)
if A.is_sparse():
row_sums = {}
for (i,j), entry in A.dict().iteritems():
row_sums[i] = row_sums.get(i, 0) + entry
for i in range(A.nrows()):
D[i,i] += row_sums.get(i, 0)
else:
row_sums=[sum(v) for v in A.rows()]
for i in range(A.nrows()):
D[i,i] += row_sums[i]
return D + A
qc = sorted(Q(graphs.CycleGraph(n)).eigenvalues())
qg = sorted(Q(g).eigenvalues())
for qci, qgi in zip(qc, qg):
if qci > qgi:
return False
return True
def is_two_connected(g):
"""
Returns True if the graph is 2-connected and False otherwise. A graph is
2-connected if the removal of any single vertex gives a connected graph.
By definition a graph on 2 or less vertices is not 2-connected.
sage: is_two_connected(graphs.CycleGraph(5))
True
sage: is_two_connected(graphs.PathGraph(5))
False
sage: is_two_connected(graphs.CompleteGraph(2))
False
sage: is_two_connected(graphs.CompleteGraph(1))
False
"""
if g.order() <= 2:
return False
from itertools import combinations
for s in combinations(g.vertices(), g.order() - 1):
if not g.subgraph(s).is_connected():
return False
return True
def is_three_connected(g):
"""
Returns True if the graph is 3-connected and False otherwise. A graph is
3-connected if the removal of any single vertex or any pair of vertices
gives a connected graph. By definition a graph on 3 or less vertices is
not 3-connected.
sage: is_three_connected(graphs.PetersenGraph())
True
sage: is_three_connected(graphs.CompleteGraph(4))
True
sage: is_three_connected(graphs.CycleGraph(5))
False
sage: is_three_connected(graphs.PathGraph(5))
False
sage: is_three_connected(graphs.CompleteGraph(3))
False
sage: is_three_connected(graphs.CompleteGraph(2))
False
sage: is_three_connected(graphs.CompleteGraph(1))
False
"""
if g.order() <= 3:
return False
from itertools import combinations
for s in combinations(g.vertices(), g.order() - 2):
if not g.subgraph(s).is_connected():
return False
return True
def is_lindquester(g):
k = vertex_con(g)
if k < 2:
return False
D = g.distance_all_pairs()
n = g.order()
V = g.vertices()
for i in range(n):
for j in range(i):
if D[V[i]][V[j]] == 2:
if len(neighbors_set(g,[V[i],V[j]])) < (2*n-1)/3.0:
return False
return True
def is_complete(g):
n = g.order()
e = g.size()
if not g.has_multiple_edges():
return e == n*(n-1)/2
D = g.distance_all_pairs()
for i in range(n):
for j in range(i):
if D[V[i]][V[j]] != 1:
return False
return True
def has_c4(g):
return g.subgraph_search(c4, induced=True) is not None
def is_c4_free(g):
return not has_c4(g)
def has_paw(g):
return g.subgraph_search(paw, induced=True) is not None
def is_paw_free(g):
return not has_paw(g)
def has_dart(g):
return g.subgraph_search(dart, induced=True) is not None
def is_dart_free(g):
return not has_dart(g)
def is_p4_free(g):
return not has_p4(g)
def has_p4(g):
return g.subgraph_search(p4, induced=True) is not None
def has_kite(g):
return g.subgraph_search(kite, induced=True) is not None
def is_kite_free(g):
return not has_kite(g)
def has_claw(g):
return g.subgraph_search(graphs.ClawGraph(), induced=True) is not None
def is_claw_free(g):
return not has_claw(g)
def has_H(g):
return g.subgraph_search(killer, induced=True) is not None
def is_H_free(g):
return not has_H(g)
def has_fork(g):
return g.subgraph_search(fork, induced=True) is not None
def is_fork_free(g):
return not has_fork(g)
def is_biclique(g):
"""
a graph is a biclique if the vertices can be partitioned into 2 sets that induce cliques
sage: is_biclique(p4)
True
sage: is_biclique(bow_tie)
True
"""
gc = g.complement()
return gc.is_bipartite()
def has_perfect_matching(g):
n = g.order()
if n%2 == 1:
return False
nu = g.matching(value_only=True)
if 2*nu == n:
return True
else:
return False
def has_radius_equal_diameter(g):
return g.radius() == g.diameter()
def has_residue_equals_alpha(g):
return residue(g) == independence_number(g)
def is_not_forest(g):
return not g.is_forest()
def bipartite_double_cover(g):
return g.tensor_product(graphs.CompleteGraph(2))
def closed_neighborhood(g, verts):
if isinstance(verts, list):
neighborhood = []
for v in verts:
neighborhood += [v] + g.neighbors(v)
return list(set(neighborhood))
else:
return [verts] + g.neighbors(verts)
def has_empty_KE_part(g):
b = bipartite_double_cover(g)
alpha = b.order() - b.matching(value_only=True)
for v in g.vertices():
test = b.copy()
test.delete_vertices(closed_neighborhood(b,[(v,0), (v,1)]))
alpha_test = test.order() - test.matching(value_only=True) + 2
if alpha_test == alpha:
return False
return True
def is_bicritical(g):
return has_empty_KE_part(g)
def is_class1(g):
return chromatic_index(g) == max(g.degree())
def is_class2(g):
return not(chromatic_index(g) == max(g.degree()))
def is_cubic(g):
D = g.degree()
return min(D) == 3 and max(D) == 3
def is_anti_tutte(g):
if not g.is_connected():
return False
return independence_number(g) <= g.diameter() + g.girth()
def is_anti_tutte2(g):
if not g.is_connected():
return False
return independence_number(g) <= domination_number(g) + g.radius()- 1
def diameter_equals_twice_radius(g):
if not g.is_connected():
return False
return g.diameter() == 2*g.radius()
def diameter_equals_radius(g):
if not g.is_connected():
return False
return g.diameter() == g.radius()
def diameter_equals_two(g):
if not g.is_connected():
return False
return g.diameter() == 2
def has_lovasz_theta_equals_alpha(g):
if g.lovasz_theta() == independence_number(g):
return True
else:
return False
def has_lovasz_theta_equals_cc(g):
if g.lovasz_theta() == clique_covering_number(g):
return True
else:
return False
def is_chvatal_erdos(g):
return independence_number(g) <= vertex_con(g)
def is_locally_connected(g):
V = g.vertices()
for v in V:
N = g.neighbors(v)
if len(N) > 0:
GN = g.subgraph(N)
if not GN.is_connected():
return False
return True
def matching_covered(g):
g = g.copy()
nu = matching_number(g)
E = g.edges()
for e in E:
g.delete_edge(e)
nu2 = matching_number(g)
if nu != nu2:
return False
g.add_edge(e)
return True
def radius_greater_than_center(g):
if not g.is_connected() or g.radius() <= card_center(g):
return False
else:
return True
def avg_distance_greater_than_girth(g):
if not g.is_connected() or g.average_distance() <= g.girth():
return False
else:
return True
def chi_equals_min_theory(g):
chromatic_upper_theory = [brooks, wilf, welsh_powell, szekeres_wilf]
min_theory = min([f(g) for f in chromatic_upper_theory])
chi = chromatic_num(g)
if min_theory == chi:
return True
else:
return False
def is_heliotropic_plant(g):
return (independence_number(g) == card_positive_eigenvalues(g))
def is_geotropic_plant(g):
return (independence_number(g) == card_negative_eigenvalues(g))
def is_traceable(g):
gadd = g.join(Graph(1),labels="integers")
return gadd.is_hamiltonian()
def has_residue_equals_two(g):
return residue(g) == 2
def is_chordal_or_not_perfect(g):
if g.is_chordal():
return true
else:
return not g.is_perfect()
def has_alpha_residue_equal_two(g):
if residue(g) != 2:
return false
else:
return independence_number(g) == 2
def alpha_leq_order_over_two(g):
return (2*independence_number(g) <= g.order())
def order_leq_twice_max_degree(g):
return (g.order() <= 2*max(g.degree()))
def is_chromatic_index_critical(g):
if not g.is_connected():
return False
Delta = max(g.degree())
chi_e = chromatic_index(g)
if chi_e != Delta + 1:
return False
lg=g.line_graph()
equiv_lines = lg.automorphism_group(return_group=False,orbits=true)
equiv_lines_representatives = [orb[0] for orb in equiv_lines]
for e in equiv_lines_representatives:
gc = copy(g)
gc.delete_edge(e)
chi_e_prime = chromatic_index(gc)
if not chi_e_prime < chi_e:
return False
return True
def is_alpha_critical(g):
alpha = independence_number(g)
for e in g.edges():
gc = copy(g)
gc.delete_edge(e)
alpha_prime = independence_number(gc)
if alpha_prime <= alpha:
return False
return True
def is_KE(g):
return g.order() == len(find_KE_part(g))
def is_independence_irreducible(g):
return g.order() == card_independence_irreducible_part(g)
def is_factor_critical(g):
"""
a graph is factor-critical if order is odd and removal of any vertex gives graph with perfect matching
is_factor_critical(p3)
False
sage: is_factor_critical(c5)
True
"""
if g.order() % 2 == 0:
return False
for v in g.vertices():
gc = copy(g)
gc.delete_vertex(v)
if not has_perfect_matching(gc):
return False
return True
def find_twins_of_vertex(g,v):
L = []
V = g.vertices()
D = g.distance_all_pairs()
for i in range(g.order()):
w = V[i]
if D[v][w] == 2 and g.neighbors(v) == g.neighbors(w):
L.append(w)
return L
def has_twin(g):
t = find_twin(g)
if t == None:
return False
else:
return True
def is_twin_free(g):
return not has_twin(g)
def find_twin(g):
V = g.vertices()
for v in V:
Nv = set(g.neighbors(v))
for w in V:
Nw = set(g.neighbors(w))
if v not in Nw and Nv == Nw:
return (v,w)
return None
def find_neighbor_twins(g):
V = g.vertices()
for v in V:
Nv = g.neighbors(v)
for w in Nv:
if set(closed_neighborhood(g,v)) == set(closed_neighborhood(g,w)):
return (v,w)
return None
def find_neighbor_twin(g, T):
gT = g.subgraph(T)
for v in T:
condition = False
Nv = set(g.neighbors(v))
NvT = set(gT.neighbors(v))
for w in Nv:
NwT = set(g.neighbors(w)).intersection(set(T))
if w not in T and NvT.issubset(NwT):
twin = w
T.append(w)
condition = True
break
if condition == True:
break
def iterative_neighbor_twins(g, T):
T2 = copy(T)
find_neighbor_twin(g, T)
while T2 != T:
T2 = copy(T)
find_neighbor_twin(g, T)
return T
def is_cycle(g):
return g.is_isomorphic(graphs.CycleGraph(g.order()))
def is_pebbling_class0(g):
for hkey in class0graphs_dict:
h = Graph(class0graphs_dict[hkey])
if g.is_isomorphic(h):
return True
return False
def girth_greater_than_2log(g):
return bool(g.girth() > 2*log(g.order(),2))
def szekeres_wilf_equals_chromatic_number(g):
return szekeres_wilf(g) == g.chromatic_number()
def localise(f):
"""
This function takes a property (i.e., a function taking only a graph as an argument) and
returns the local variant of that property. The local variant is True if the property is
True for the neighbourhood of each vertex and False otherwise.
"""
def localised_function(g):
return all((f(g.subgraph(g.neighbors(v))) if g.neighbors(v) else True) for v in g.vertices())
if hasattr(f, '__name__'):
if f.__name__.startswith('is_'):
localised_function.__name__ = 'is_locally' + f.__name__[2:]
elif f.__name__.startswith('has_'):
localised_function.__name__ = 'has_locally' + f.__name__[2:]
else:
localised_function.__name__ = 'localised_' + f.__name__
return localised_function
is_locally_dirac = localise(is_dirac)
is_locally_bipartite = localise(Graph.is_bipartite)
def is_locally_two_connected(g):
V = g.vertices()
for v in V:
N = g.neighbors(v)
if len(N) > 0:
GN = g.subgraph(N)
if not is_two_connected(GN):
return False
return True
def has_equal_invariants(invar1, invar2, name=None):
"""
This function takes two invariants as an argument and returns the property that these invariants are equal.
Optionally a name for the new function can be provided as a third argument.
"""
def equality_checker(g):
return invar1(g) == invar2(g)
if name is not None:
equality_checker.__name__ = name
elif hasattr(invar1, '__name__') and hasattr(invar2, '__name__'):
equality_checker.__name__ = 'has_{}_equals_{}'.format(invar1.__name__, invar2.__name__)
else:
raise ValueError('Please provide a name for the new function')
return equality_checker
def has_leq_invariants(invar1, invar2, name=None):
"""
This function takes two invariants as an argument and returns the property that the first invariant is
less than or equal to the second invariant.
Optionally a name for the new function can be provided as a third argument.
"""
def comparator(g):
return invar1(g) <= invar2(g)
if name is not None:
comparator.__name__ = name
elif hasattr(invar1, '__name__') and hasattr(invar2, '__name__'):
comparator.__name__ = 'has_{}_leq_{}'.format(invar1.__name__, invar2.__name__)
else:
raise ValueError('Please provide a name for the new function')
return comparator
def has_Havel_Hakimi_property(g, v):
"""
This function returns whether the vertex v in the graph g has the Havel-Hakimi
property as defined in [1]. A vertex has the Havel-Hakimi property if it has
maximum degree and the minimum degree of its neighbours is at least the maximum
degree of its non-neigbours.
[1] Graphs with the strong Havel-Hakimi property, M. Barrus, G. Molnar, Graphs
and Combinatorics, 2016, http://dx.doi.org/10.1007/s00373-015-1674-7
Every vertex in a regular graph has the Havel-Hakimi property::
sage: P = graphs.PetersenGraph()
sage: for v in range(10):
....: has_Havel_Hakimi_property(P,v)
True
True
True
True
True
True
True
True
True
True
sage: has_Havel_Hakimi_property(Graph([[0,1,2,3],lambda x,y: False]),0)
True
sage: has_Havel_Hakimi_property(graphs.CompleteGraph(5),0)
True
"""
if max_degree(g) > g.degree(v): return False
if len(g.neighbors(v)) == 0: return True
if len(g.neighbors(v)) == len(g.vertices()) - 1: return True
return (min(g.degree(nv) for nv in g.neighbors(v)) >=
max(g.degree(nnv) for nnv in g.vertices() if nnv != v and nnv not in g.neighbors(v)))
def has_strong_Havel_Hakimi_property(g):
"""
This function returns whether the graph g has the strong Havel-Hakimi property
as defined in [1]. A graph has the strong Havel-Hakimi property if in every
induced subgraph H of G, every vertex of maximum degree has the Havel-Hakimi
property.
[1] Graphs with the strong Havel-Hakimi property, M. Barrus, G. Molnar, Graphs
and Combinatorics, 2016, http://dx.doi.org/10.1007/s00373-015-1674-7
The graph obtained by connecting two cycles of length 3 by a single edge has
the strong Havel-Hakimi property::
sage: has_strong_Havel_Hakimi_property(Graph('E{CW'))
True
"""
for S in Subsets(g.vertices()):
if len(S)>2:
H = g.subgraph(S)
Delta = max_degree(H)
if any(not has_Havel_Hakimi_property(H, v) for v in S if H.degree(v) == Delta):
return False
return True
invariant_relation_properties = [has_leq_invariants(f,g) for f in invariants for g in invariants if f != g]
efficiently_computable_properties = [Graph.is_regular, Graph.is_planar,
Graph.is_forest, Graph.is_eulerian, Graph.is_connected, Graph.is_clique,
Graph.is_circular_planar, Graph.is_chordal, Graph.is_bipartite,
Graph.is_cartesian_product,Graph.is_distance_regular, Graph.is_even_hole_free,
Graph.is_gallai_tree, Graph.is_line_graph, Graph.is_overfull, Graph.is_perfect,
Graph.is_split, Graph.is_strongly_regular, Graph.is_triangle_free,
Graph.is_weakly_chordal, is_dirac, is_ore, is_haggkvist_nicoghossian,
is_generalized_dirac, is_van_den_heuvel, is_two_connected, is_three_connected,
is_lindquester, is_claw_free, has_perfect_matching, has_radius_equal_diameter,
is_not_forest, is_fan, is_cubic, diameter_equals_twice_radius,
diameter_equals_radius, is_locally_connected, matching_covered, is_locally_dirac,
is_locally_bipartite, is_locally_two_connected, Graph.is_interval, has_paw,
is_paw_free, has_p4, is_p4_free, has_dart, is_dart_free, has_kite, is_kite_free,
has_H, is_H_free, has_residue_equals_two, order_leq_twice_max_degree,
alpha_leq_order_over_two, is_factor_critical, is_independence_irreducible,
has_twin, is_twin_free, diameter_equals_two, girth_greater_than_2log, is_cycle,
pairs_have_unique_common_neighbor, has_star_center, is_complement_of_chordal, has_c4, is_c4_free]
intractable_properties = [Graph.is_hamiltonian, Graph.is_vertex_transitive,
Graph.is_edge_transitive, has_residue_equals_alpha, Graph.is_odd_hole_free,
Graph.is_semi_symmetric, Graph.is_line_graph, is_planar_transitive, is_class1,
is_class2, is_anti_tutte, is_anti_tutte2, has_lovasz_theta_equals_cc,
has_lovasz_theta_equals_alpha, is_chvatal_erdos, is_heliotropic_plant,
is_geotropic_plant, is_traceable, is_chordal_or_not_perfect,
has_alpha_residue_equal_two]
removed_properties = [is_pebbling_class0]
properties = efficiently_computable_properties + intractable_properties
properties_plus = efficiently_computable_properties + intractable_properties + invariant_relation_properties
invariants_from_properties = [make_invariant_from_property(property) for property in properties]
invariants_plus = invariants + invariants_from_properties
p3 = graphs.PathGraph(3)
p3.name(new = "p3")
k3_3=graphs.CompleteBipartiteGraph(3,3)
k3_3.name(new = "k3_3")
c4c4=graphs.CycleGraph(4)
for i in [4,5,6]:
c4c4.add_vertex()
c4c4.add_edge(3,4)
c4c4.add_edge(5,4)
c4c4.add_edge(5,6)
c4c4.add_edge(6,3)
c4c4.name(new="c4c4")
c5c5=graphs.CycleGraph(5)
for i in [5,6,7,8]:
c5c5.add_vertex()
c5c5.add_edge(0,5)
c5c5.add_edge(0,8)
c5c5.add_edge(6,5)
c5c5.add_edge(6,7)
c5c5.add_edge(7,8)
c5c5.name(new="c5c5")
c3p2=graphs.CycleGraph(3)
c3p2.add_vertex()
c3p2.add_edge(0,3)
c3p2.name(new="c3p2")
K4a=graphs.CompleteGraph(4)
K4b=graphs.CompleteGraph(4)
K4a.delete_edge(0,1)
K4b.delete_edge(0,1)
regular_non_trans = K4a.disjoint_union(K4b)
regular_non_trans.add_edge((0,0),(1,1))
regular_non_trans.add_edge((0,1),(1,0))
regular_non_trans.name(new="regular_non_trans")
c6ee = graphs.CycleGraph(6)
c6ee.add_edges([(1,5), (2,4)])
c6ee.name(new="c6ee")
c5chord = graphs.CycleGraph(5)
c5chord.add_edge(0,3)
c5chord.name(new="c5chord")
c6eee = copy(c6ee)
c6eee.add_edge(0,3)
c6eee.name(new="c6eee")
c8chorded = graphs.CycleGraph(8)
c8chorded.add_edge(0,4)
c8chorded.add_edge(1,7)
c8chorded.add_edge(2,6)
c8chorded.add_edge(3,5)
c8chorded.name(new="c8chorded")
c8chords = graphs.CycleGraph(8)
c8chords.add_edge(1,6)
c8chords.add_edge(2,5)
c8chords.name(new="c8chords")
c8chords = graphs.CycleGraph(8)
c8chords.add_edge(1,6)
c8chords.add_edge(2,5)
c8chords.name(new="c8chords")
prism = graphs.CycleGraph(6)
prism.add_edge(0,2)
prism.add_edge(3,5)
prism.add_edge(1,4)
prism.name(new="prism")
prismsub = copy(prism)
prismsub.subdivide_edge(1,4,1)
prismsub.name(new="prismsub")
prismy = graphs.CycleGraph(8)
prismy.add_edge(2,5)
prismy.add_edge(0,3)
prismy.add_edge(4,7)
prismy.name(new="prismy")
sixfour = graphs.CycleGraph(10)
sixfour.add_edge(1,9)
sixfour.add_edge(0,2)
sixfour.add_edge(3,8)
sixfour.add_edge(4,6)
sixfour.add_edge(5,7)
sixfour.name(new="sixfour")
c24 = Graph('WsP@H?PC?O`?@@?_?GG@??CC?G??GG?E???o??B???E???F')
c24.name(new="c24")
c26 = Graph('YsP@H?PC?O`?@@?_?G?@??CC?G??GG?E??@_??K???W???W???H???E_')
c26.name(new="c26")
"""
The Holton-McKay graph is the smallest planar cubic hamiltonian graph with an edge
that is not contained in a hamiltonian cycle. It has 24 vertices and the edges (0,3)
and (4,7) are not contained in a hamiltonian cycle. This graph was mentioned in
D. A. Holton and B. D. McKay, Cycles in 3-connected cubic planar graphs II, Ars
Combinatoria, 21A (1986) 107-114.
sage: holton_mckay
holton_mckay: Graph on 24 vertices
sage: holton_mckay.is_planar()
True
sage: holton_mckay.is_regular()
True
sage: max(holton_mckay.degree())
3
sage: holton_mckay.is_hamiltonian()
True
sage: holton_mckay.radius()
4
sage: holton_mckay.diameter()
6
"""
holton_mckay = Graph('WlCGKS??G?_D????_?g?DOa?C?O??G?CC?`?G??_?_?_??L')
holton_mckay.name(new="holton_mckay")
z1 = graphs.CycleGraph(3)
z1.add_edge(0,3)
z1.name(new="z1")
kratsch_lehel_muller = graphs.PathGraph(12)
kratsch_lehel_muller.add_edge(0,5)
kratsch_lehel_muller.add_edge(6,11)
kratsch_lehel_muller.add_edge(4,9)
kratsch_lehel_muller.add_edge(1,10)
kratsch_lehel_muller.add_edge(2,7)
kratsch_lehel_muller.name(new="kratsch_lehel_muller")
c6xc6 = graphs.CycleGraph(6).cartesian_product(graphs.CycleGraph(6))
c6xc6.name(new="c6xc6")
gould = Graph('S~dg?CB?wC_L????_?W?F??c?@gOOOGGK')
gould.name(new="gould")
throwing = Graph('J~wWGGB?wF_')
throwing.name(new="throwing")
throwing2 = Graph("K~wWGKA?gB_N")
throwing2.name(new="throwing2")
throwing3 = Graph("K~wWGGB?oD_N")
throwing3.name(new="throwing3")
tent = graphs.CycleGraph(4).join(Graph(1),labels="integers")
tent.name(new="tent")
c6subk4 = graphs.CycleGraph(6)
c6subk4.add_edge(1,5)
c6subk4.add_edge(1,4)
c6subk4.add_edge(2,5)
c6subk4.add_edge(2,4)
c6subk4.name(new="c6subk4")
bridge = Graph("DU{")
bridge.name(new="bridge")
non_ham_over = Graph("HCQRRQo")
non_ham_over.name(new="non_ham_over")
ryan = Graph("WxEW?CB?I?_R????_?W?@?OC?AW???O?C??B???G?A?_??R")
ryan.name(new="ryan")
inp = Graph('J?`FBo{fdb?')
inp.name(new="inp")
p10k4=Graph('MhCGGC@?G?_@_B?B_')
p10k4.name(new="p10k4")
s13e = Graph('M{aCCA?_C?O?_?_??')
s13e.name(new="s13e")
ryan2=graphs.CirculantGraph(50,[1,3])
ryan2.name(new="circulant_50_1_3")
s22e = graphs.StarGraph(22)
s22e.add_edge(1,2)
s22e.name(new="s22e")
c100 = Graph("~?@csP@@?OC?O`?@?@_?O?A??W??_??_G?O??C??@_??C???G???G@??K???A????O???@????A????A?G??B?????_????C?G???O????@_?????_?????O?????C?G???@_?????E??????G??????G?G????C??????@???????G???????o??????@???????@????????_?_?????W???????@????????C????????G????????G?G??????E????????@_????????K?????????_????????@?@???????@?@???????@_?????????G?????????@?@????????C?C????????W??????????W??????????C??????????@?@?????????G???????????_??????????@?@??????????_???????????O???????????C?G??????????O???????????@????????????A????????????A?G??????????@_????????????W????????????@_????????????E?????????????E?????????????E?????????????B??????????????O?????????????A@?????????????G??????????????OG?????????????O??????????????GC?????????????A???????????????OG?????????????@?_?????????????B???????????????@_???????????????W???????????????@_???????????????F")
c100.name(new="c100")
dc64_g6string ="~?@?JXxwm?OJ@wESEYMMbX{VDokGxAWvH[RkTAzA_Tv@w??wF]?oE\?OAHoC_@A@g?PGM?AKOQ??ZPQ?@rgt??{mIO?NSD_AD?mC\
O?J?FG_FOOEw_FpGA[OAxa?VC?lWOAm_DM@?Mx?Y{A?XU?hwA?PM?PW@?G@sGBgl?Gi???C@_FP_O?OM?VMA_?OS?lSB??PS?`sU\
??Gx?OyF_?AKOCN`w??PA?P[J??@C?@CU_??AS?AW^G??Ak?AwVZg|?Oy_@?????d??iDu???C_?D?j_???M??[Bl_???W??oEV?\
???O??_CJNacABK?G?OAwP??b???GNPyGPCG@???"
dc64 = Graph(dc64_g6string)
dc64.name(new="dc64")
try:
s = load(os.environ['HOME'] +'/objects-invariants-properties/dc1024_g6string.sobj')
print "loaded graph dc1024"
dc1024 = Graph(s)
dc1024.name(new="dc1024")
except:
print "couldn't load dc1024_g6string.sobj"
try:
s = load(os.environ['HOME'] +'/objects-invariants-properties/dc2048_g6string.sobj')
print "loaded graph dc2048"
dc2048 = Graph(s)
dc2048.name(new="dc2048")
except:
print "couldn't load dc2048_g6string.sobj"
starfish = Graph('N~~eeQoiCoM?Y?U?F??')
starfish.name(new="starfish")
difficult11 = Graph('J?`FBo{fdb?')
difficult11.name(new="difficult11")
c5k3=Graph('FheCG')
c5k3.name(new="c5k3")
c3mycielski = Graph('FJnV?')
c3mycielski.name(new="c3mycieski")
c3mycielski4 = Graph('~??~??GWkYF@BcuIsJWEo@s?N?@?NyB`qLepJTgRXkAkU?JPg?VB_?W[??Ku??BU_??ZW??@u???Bs???Bw???A??F~~_B}?^sB`o[MOuZErWatYUjObXkZL_QpWUJ?CsYEbO?fB_w[?A`oCM??DL_Hk??DU_Is??Al_Dk???l_@k???Ds?M_???V_?{????oB}?????o[M?????WuZ?????EUjO?????rXk?????BUJ??????EsY??????Ew[??????B`o???????xk???????FU_???????\\k????????|_????????}_????????^_?????????')
c3mycielski4.name(new="c3mycielski4")
paw=Graph('C{')
paw.name(new="paw")
binary_octahedron = Graph('L]lw??B?oD_Noo')
binary_octahedron.name(new = "binary_octahedron")
paw_x_paw = paw.cartesian_product(paw)
paw_x_paw.name(new = "paw_x_paw")
kite = Graph('Cn')
kite.name(new="kite")
dart = Graph('DnC')
dart.name(new="dart")
p4=Graph('Ch')
p4.name(new="p4")
p5 = graphs.PathGraph(5)
p5.name(new = "p5")
c9 = graphs.CycleGraph(9)
c9.name(new = "c9")
ce3=Graph("Gr`HOk")
ce3.name(new = "ce3")
ce2=Graph("HdGkCA?")
ce2.name(new = "ce2")
c6 = graphs.CycleGraph(6)
c6.name(new = "c6")
ce4=Graph("G~sNp?")
ce4.name(new = "ce4")
ce5=Graph("X~}AHKVB{GGPGRCJ`B{GOO`C`AW`AwO`}CGOO`AHACHaCGVACG^")
ce5.name(new = "ce5")
ce6 = Graph("H??E@cN")
ce6.name(new = "ce6")
ce7 = Graph("FpGK?")
ce7.name(new = "ce7")
ce8 = Graph('IxCGGC@_G')
ce8.name(new = "ce8")
ce9 = Graph('IhCGGD?G?')
ce9.name(new = "ce9")
ce10=Graph('KxkGGC@?G?o@')
ce10.name(new = "ce10")
ce11 = Graph("E|OW")
ce11.name(new = "ce11")
ce12 = Graph("Edo_")
ce12.name(new = "ce12")
ce13 = Graph("ExOG")
ce13.name(new = "ce13")
ce14 = Graph('IhCGGC_@?')
ce14.name(new = "IhCGGC_@?")
k5pendant = Graph('E~}?')
k5pendant.name(new="k5pendant")
killer = Graph('EgSG')
killer.name(new="killer")
alon_seymour=Graph([[0..63], lambda x,y : operator.xor(x,y) not in (0,1,2,4,8,16,32,63)])
alon_seymour.name(new="alon_seymour")
k3 = graphs.CompleteGraph(3)
k3.name(new="k3")
k4 = graphs.CompleteGraph(4)
k4.name(new="k4")
k5 = graphs.CompleteGraph(5)
k5.name(new="k5")
k6 = graphs.CompleteGraph(6)
k6.name(new="k6")
c4 = graphs.CycleGraph(4)
c4.name(new="c4")
p2 = graphs.PathGraph(2)
p2.name(new="p2")
p6 = graphs.PathGraph(6)
p6.name(new="p6")
s3 = graphs.StarGraph(3)
s3.name(new="s3")
k10 = graphs.CompleteGraph(10)
k10.name(new="k10")
c60 = graphs.BuckyBall()
c60.name(new="c60")
moser = Graph('Fhfco')
moser.name(new = "moser")
holt = graphs.HoltGraph()
holt.name(new = "holt")
golomb = Graph("I?C]dPcww")
golomb.name(new = "golomb")
edge_critical_5=graphs.CycleGraph(5)
edge_critical_5.add_edge(0,3)
edge_critical_5.add_edge(1,4)
edge_critical_5.name(new="edge_critical_5")
heather = graphs.CompleteGraph(4)
heather.add_vertex()
heather.add_vertex()
heather.add_edge(0,4)
heather.add_edge(5,4)
heather.name(new="heather")
pete = graphs.PetersenGraph()
ryan3=graphs.CycleGraph(15)
for i in range(15):
for j in [1,2,3]:
ryan3.add_edge(i,(i+j)%15)
ryan3.add_edge(i,(i-j)%15)
ryan3.name(new="ryan3")
sylvester = Graph('Olw?GCD@o??@?@?A_@o`A')
sylvester.name(new="sylvester")
fork=graphs.PathGraph(4)
fork.add_vertex()
fork.add_edge(1,4)
fork.name(new="fork")
edge_critical_11_1 = graphs.CycleGraph(11)
edge_critical_11_1.add_edge(0,2)
edge_critical_11_1.add_edge(1,6)
edge_critical_11_1.add_edge(3,8)
edge_critical_11_1.add_edge(5,9)
edge_critical_11_1.name(new="edge_critical_11_1")
edge_critical_11_2 = graphs.CycleGraph(11)
edge_critical_11_2.add_edge(0,2)
edge_critical_11_2.add_edge(3,7)
edge_critical_11_2.add_edge(6,10)
edge_critical_11_2.add_edge(4,9)
edge_critical_11_2.name(new="edge_critical_11_2")
pete_minus=graphs.PetersenGraph()
pete_minus.delete_vertex(9)
pete_minus.name(new="pete_minus")
bow_tie = Graph(5)
bow_tie.add_edge(0,1)
bow_tie.add_edge(0,2)
bow_tie.add_edge(0,3)
bow_tie.add_edge(0,4)
bow_tie.add_edge(1,2)
bow_tie.add_edge(3,4)
bow_tie.name(new = "bow_tie")
"""
The Haemers graph was considered by Haemers who showed that alpha(G)=theta(G)<vartheta(G).
The graph is a 108-regular graph on 220 vertices. The vertices correspond to the 3-element
subsets of {1,...,12} and two such vertices are adjacent whenever the subsets
intersect in exactly one element.
sage: haemers
haemers: Graph on 220 vertices
sage: haemers.is_regular()
True
sage: max(haemers.degree())
108
"""
haemers = Graph([Subsets(12,3), lambda s1,s2: len(s1.intersection(s2))==1])
haemers.relabel()
haemers.name(new="haemers")
"""
The Pepper residue graph was described by Ryan Pepper in personal communication.
It is a graph which demonstrates that the residue is not monotone. The graph is
constructed by taking the complete graph on 3 vertices and attaching a pendant
vertex to each of its vertices, then taking two copies of this graph, adding a
vertex and connecting it to all the pendant vertices. This vertex has degree
sequence [6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2] which gives residue equal to 4.
By removing the central vertex with degree 6, you get a graph with degree
sequence [3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1] which has residue equal to 5.
sage: pepper_residue_graph
pepper_residue_graph: Graph on 13 vertices
sage: sorted(pepper_residue_graph.degree(), reverse=True)
[6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2]
sage: residue(pepper_residue_graph)
4
sage: residue(pepper_residue_graph.subgraph(vertex_property=lambda v:pepper_residue_graph.degree(v)<6))
5
"""
pepper_residue_graph = graphs.CompleteGraph(3)
pepper_residue_graph.add_edges([(i,i+3) for i in range(3)])
pepper_residue_graph = pepper_residue_graph.disjoint_union(pepper_residue_graph)
pepper_residue_graph.add_edges([(0,v) for v in pepper_residue_graph.vertices() if pepper_residue_graph.degree(v)==1])
pepper_residue_graph.relabel()
pepper_residue_graph.name(new="pepper_residue_graph")
"""
The Barrus graph was suggested by Mike Barrus in "Havel-Hakimi residues of Unigraphs" (2012) as an example of a graph whose residue (2) is
less than the independence number of any realization of the degree sequence. The degree sequence is [4^8,2].
The realization is the one given by reversing the Havel-Hakimi process.
sage: barrus_graph
barrus_graph: Graph on 9 vertices
sage: residue(barrus_graph)
2
sage: independence_number(barrus_graph)
3
"""
barrus_graph = Graph('HxNEG{W')
barrus_graph.name(new = "barrus_graph")
k4e2split = graphs.CompleteGraph(4)
k4e2split.add_vertices([4,5])
k4e2split.add_edge(4,0)
k4e2split.add_edge(4,1)
k4e2split.add_edge(5,2)
k4e2split.add_edge(5,3)
k4e2split.name(new = "k4e2split")
houseX=graphs.HouseXGraph()
houseX.name(new = "houseX")
triangle_star = Graph("H}qdB@_")
triangle_star.name(new = "triangle_star")
def flower(n):
g = graphs.StarGraph(2*n)
for x in range(n):
v = 2*x+1
g.add_edge(v,v+1)
return g
flower_with_3_petals = flower(3)
flower_with_3_petals.name(new = "flower_with_3_petals")
flower_with_4_petals = flower(4)
flower_with_4_petals.name(new = "flower_with_4_petals")
alpha_critical_graph_names = ['A_','Bw', 'C~', 'Dhc', 'D~{', 'E|OW', 'E~~w', 'FhCKG', 'F~[KG', 'FzEKW', 'Fn[kG', 'F~~~w', 'GbL|TS', 'G~?mvc', 'GbMmvG', 'Gb?kTG', 'GzD{Vg', 'Gb?kR_', 'GbqlZ_', 'GbilZ_', 'G~~~~{', 'GbDKPG', 'HzCGKFo', 'H~|wKF{', 'HnLk]My', 'HhcWKF_', 'HhKWKF_', 'HhCW[F_', 'HxCw}V`', 'HhcGKf_', 'HhKGKf_', 'Hh[gMEO', 'HhdGKE[', 'HhcWKE[', 'HhdGKFK', 'HhCGGE@', 'Hn[gGE@', 'Hn^zxU@', 'HlDKhEH', 'H~~~~~~', 'HnKmH]N', 'HnvzhEH', 'HhfJGE@', 'HhdJGM@', 'Hj~KHeF', 'HhdGHeB', 'HhXg[EO', 'HhGG]ES', 'H~Gg]f{', 'H~?g]vs', 'H~@w[Vs', 'Hn_k[^o']
alpha_critical_easy = []
for s in alpha_critical_graph_names:
g = Graph(s)
g.name(new="alpha_critical_"+ s)
alpha_critical_easy.append(g)
L = ['FhCKG', 'FzCKW', 'FzNKW', 'FlSkG', 'Fn]kG', 'FlLKG', 'FnlkG', 'F~|{G', 'FnlLG', 'F~|\\G', 'FnNLG', 'F~^LW', 'Fll\\G', 'FllNG', 'F~l^G', 'F~|^w', 'F~~^W', 'Fnl^W', 'FlNNG', 'F|\\Kg', 'F~^kg', 'FlKMG']
chromatic_index_critical_7 = []
for s in L:
g=Graph(s)
g.name(new="chromatic_index_critical_7_" + s)
chromatic_index_critical_7.append(g)
import pickle, os, os.path
try:
class0graphs_dict = pickle.load(open(os.environ['HOME'] + "/objects-invariants-properties/class0graphs_dictionary.pickle","r"))
except:
class0graphs_dict = {}
class0graphs = []
for d in class0graphs_dict:
g = Graph(class0graphs_dict[d])
g.name(new = d)
class0graphs.append(g)
class0small = [g for g in class0graphs if g.order() < 30]
c5=graphs.CycleGraph(5)
c5.name(new = "c5")
graph_objects = [paw, kite, p4, dart, k3, k4, k5, c6ee, c5chord, graphs.DodecahedralGraph(), c8chorded, c8chords, graphs.ClebschGraph(), prismy, c24, c26, c60, c6xc6, holton_mckay, sixfour, c4, graphs.PetersenGraph(), p2, graphs.TutteGraph(), non_ham_over, throwing, throwing2, throwing3, kratsch_lehel_muller, graphs.BlanusaFirstSnarkGraph(), graphs.BlanusaSecondSnarkGraph(), graphs.FlowerSnark(), s3, ryan3, k10, graphs.MycielskiGraph(5), c3mycielski, s13e, ryan2, s22e, difficult11, graphs.BullGraph(), graphs.ChvatalGraph(), graphs.ClawGraph(), graphs.DesarguesGraph(), graphs.DiamondGraph(), graphs.FlowerSnark(), graphs.FruchtGraph(), graphs.HoffmanSingletonGraph(), graphs.HouseGraph(), graphs.OctahedralGraph(), graphs.ThomsenGraph(), pete , graphs.PappusGraph(), graphs.GrotzschGraph(), graphs.GrayGraph(), graphs.HeawoodGraph(), graphs.HerschelGraph(), graphs.CoxeterGraph(), graphs.BrinkmannGraph(), graphs.TutteCoxeterGraph(), graphs.TutteGraph(), graphs.RobertsonGraph(), graphs.FolkmanGraph(), graphs.Balaban10Cage(), graphs.PappusGraph(), graphs.TietzeGraph(), graphs.SylvesterGraph(), graphs.SzekeresSnarkGraph(), graphs.MoebiusKantorGraph(), ryan, inp, c4c4, regular_non_trans, bridge, p10k4, c100, starfish, c5k3, k5pendant, graphs.ShrikhandeGraph(), sylvester, fork, edge_critical_5, edge_critical_11_1, edge_critical_11_2, pete_minus, c5, bow_tie, pepper_residue_graph, barrus_graph, p5, c6, c9, ce3, ce4, ce5, k4e2split, flower_with_3_petals, flower_with_4_petals, paw_x_paw, graphs.WagnerGraph(), houseX, ce7, triangle_star, ce8, ce9, ce10, p3, binary_octahedron, ce11, prism, ce12, ce13, ce14] + alpha_critical_easy
alpha_critical_hard = [Graph('Hj\\x{F{')]
chromatic_index_critical_graphs = chromatic_index_critical_7 + [edge_critical_5, edge_critical_11_1, edge_critical_11_2, pete_minus]
problem_graphs = [graphs.MeredithGraph(), graphs.SchlaefliGraph(), haemers, c3mycielski4, alon_seymour] + chromatic_index_critical_7 + class0small + alpha_critical_hard
"""
graph_objects = []
for g in union_objects, idfun=Graph.graph6_string:
if not g in graph_objects:
graph_objects.append(g)
"""
def remove_duplicates(seq, idfun=None):
if idfun is None:
def idfun(x): return x
seen = {}
result = []
for item in seq:
marker = idfun(item)
if marker in seen: continue
seen[marker] = 1
result.append(item)
return result
def find_separating_invariant_relation(g, objects, property, invariants):
L = [x for x in objects if (property)(x)]
for inv1 in invariants:
for inv2 in invariants:
if inv1(g) > inv2(g) and all(inv1(x) <= inv2(x) for x in L):
return inv1.__name__, inv2.__name__
print "no separating invariants"
def test_properties_upper_bound_theory(objects, property, theory):
for g in objects:
if not property(g) and all(f(g) for f in theory):
print g.name()
def test_properties_lower_bound_theory(objects, property, theory):
for g in objects:
if property(g) and not any(f(g) for f in theory):
print g.name()
def find_coextensive_properties(objects, properties):
for p1 in properties:
for p2 in properties:
if p1 != p2 and all(p1(g) == p2(g) for g in objects):
print p1.__name__, p2.__name__
print "DONE!"
try:
graph_property_data = load(os.environ['HOME'] +'/objects-invariants-properties/graph_property_data.sobj')
print "loaded graph properties data file"
except IOError:
print "can't load graph properties sobj file"
graph_property_data = {}
def update_graph_property_data(new_objects,properties):
global graph_property_data
try:
graph_property_data = load(os.environ['HOME'] +'/objects-invariants-properties/graph_property_data.sobj')
except IOError:
print "can't load properties sobj file"
graph_property_data = {}
for g in new_objects:
print g.name()
if g.name not in graph_property_data.keys():
graph_property_data[g.name()] = {}
for prop in properties:
try:
graph_property_data[g.name()][prop.__name__]
except KeyError:
graph_property_data[g.name()][prop.__name__] = prop(g)
save(graph_property_data, "graph_property_data.sobj")
print "DONE"
try:
graph_invariant_data = load(os.environ['HOME'] +'/objects-invariants-properties/graph_invariant_data.sobj')
print "loaded graph invariants data file"
except IOError:
print "can't load graph invariant sobj file"
graph_invariant_data = {}
def update_graph_invariant_data(new_objects,invariants):
global graph_invariant_data
try:
graph_invariant_data = load(os.environ['HOME'] +'/objects-invariants-properties/graph_invariant_data.sobj')
print "loaded graph invariants data file"
except IOError:
print "can't load invariant sobj file"
graph_invariant_data = {}
for g in new_objects:
print g.name()
if g.name not in graph_invariant_data.keys():
graph_invariant_data[g.name()] = {}
for inv in invariants:
try:
graph_invariant_data[g.name()][inv.__name__]
except KeyError:
graph_invariant_data[g.name()][inv.__name__] = inv(g)
save(graph_invariant_data, "graph_invariant_data.sobj")
print "DONE"