Extended Cube Graph

1904 days ago by ddyoung

def extended_cube_graph(t,k): """ Returns an extended cube graph :t: a nonnegative integer :k: a nonnegative integer :returns: extended cube graph """ n = 2*(t+k)+8 g = graphs.CycleGraph(n) v1=[i+0 for i in range(k+2)] v2=[i+k+2 for i in range(t+2)] v3=[i+k+t+4 for i in range(k+2)] v4=[i+2*k+t+6 for i in range(t+2)] horizontal_edges = [(v2[i],v4[-i-1]) for i in range(t+2)] vertical_edges = [(v1[i],v3[-i-1]) for i in range(k+2)] g.add_edges(horizontal_edges) g.add_edges(vertical_edges) return g 
       
extended_cube_graph(1,2) 
       
def list_matrices_Z_2(g,Z,p=2): """ :g: A graph. :Z: The zero forcing number of the given graph. :returns: A set of tuples with entries corresponding to nonzero diagonal entries of a potential universally optimal matrices. :Example: sage: g=graphs.CycleGraph(7) ....: sage: list_matrices_Z_2(g,2) ....: The graph has 21 matrices that achieve minimum rank of 5 over Z_2 {(0, 1, 2), (0, 1, 2, 3, 5), (0, 1, 2, 4, 6), (0, 1, 3, 5, 6), (0, 1, 4), (0, 1, 6), (0, 2, 3, 4, 5), (0, 2, 4, 5, 6), (0, 3, 4), (0, 3, 6), (0, 5, 6), (1, 2, 3), (1, 2, 3, 4, 6), (1, 2, 5), (1, 3, 4, 5, 6), (1, 4, 5), (2, 3, 4), (2, 3, 6), (2, 5, 6), (3, 4, 5), (4, 5, 6)} """ import itertools n = g.order() integer_set = [i for i in range(n)] nonzero_set = set([ ]) for L in range(n+1): for subset in itertools.combinations(integer_set, L): A=g.am() for i in range(L): j = subset[i] A[j,j]=1 A=matrix(GF(p),A) if A.rank() == n-Z: nonzero_set.add(subset) print("The graph has {} matrices that achieve minimum rank" " of {} over Z_{}".format(len(nonzero_set),n-Z,p)) return nonzero_set 
       
C7=graphs.CycleGraph(7) P2=graphs.PathGraph(2) g=C7.cartesian_product(P2) 
       
list_matrices_Z_2(g,4) 
       
The graph has 0 matrices that achieve minimum rank of 10 over Z_2
set()
The graph has 0 matrices that achieve minimum rank of 10 over Z_2
set()