MaxNullity_ZeroForcing_Variants

364 days ago by hogben

# Sage code and examples for minimum rank/maximum nullity, variants of zero forcing, and power domination 
       
#################################### # This Sage worksheet is written by Leslie Hogben based on code written by numerous other people. # The focus of this worksheet is on minimum rank/maximum nullity, variants of zero forcing, and power domination. # Examples are from the book, # "Inverse Problems and Zero Forcing for Graphs" # by Leslie Hogben, Jehian C.H. Lin, and Bryan L. Shader # Please report errors to hogben@aimath.org and jephianlin@gmail.com # # This worksheet begins with examples, which are ready to read. # In order to run the examples for yourself, you first need to enter the function cells. # to do that, search for FUNCTIONS-HERE and enter each cell that begins F-#. ################################### 
       
#################################### # Chapter 2: Examples for Minimum rank, maximum nullity, and zero forcing # The minimum rank program implements various known bounds and cut vertex reduction. # It returns (lower bound, upper bound). # If these are equal you have the minimum rank. #################################### 
       
# Examples of computation of minimum rank of well known graph families 
       
# Path example p=graphs.PathGraph(6) minrank_bounds(p) 
       
(5, 5)
(5, 5)
# so mr(P_6)=5 and M(P_6)=1 
       
# Cycle example c=graphs.CycleGraph(5) minrank_bounds(c) 
       
(3, 3)
(3, 3)
# so mr(C_5)=3 and M(C_5)=2 
       
# Complete graph example 
       
k=graphs.CompleteGraph(5) show(k) minrank_bounds(k) 
       
(1, 1)
(1, 1)
# so mr(K_5)=1 and M(K_5)=4 
       
# Complete bipartite graph example 
       
b=graphs.CompleteBipartiteGraph(5,3) show(b) minrank_bounds(b) 
       
(2, 2)
(2, 2)
# so mr(K_{5,3})=2 and M(K_{5,3})=6 
       
# Hypercube example # The software does not always find known results. # It is known that mr(Q_d) = 2^(d-1) [AIM Minimum Rank - Special Graphs Work Group, # Zero forcing sets and the minimum rank of graphs. Lin. Alg. Appl., 428: 1628--1648, 2008]. 
       
q=graphs.CubeGraph(3) q.relabel() show(q) minrank_bounds(q) 
       
(4, 5)
(4, 5)
# We can ask for more information as to what has been found: 
       
minrank_bounds(q, all_bounds=True) 
       
({'diameter': 3,
  'forbidden minrank 2': 3,
  'rank': 0,
  'zero forcing': 4,
  'zero forcing fast': 4},
 {'clique cover': 12,
  'not outer planar': 5,
  'not path': 6,
  'order': 7,
  'rank': 8})
({'diameter': 3,
  'forbidden minrank 2': 3,
  'rank': 0,
  'zero forcing': 4,
  'zero forcing fast': 4},
 {'clique cover': 12,
  'not outer planar': 5,
  'not path': 6,
  'order': 7,
  'rank': 8})
# The first list is lower bound tests and values returned (recall n-Z(G) <= mr(G)). # The second list is upper bound tests and values returned. # Here the best lower bound is 4 = 8 - 4 = |V(Q_3)| - Z(Q_3) and # the best upper bound is 5 = |V(Q_3)| - 3 since Q_3 is not outerplanar. # in other words, 3 <= M(Q_3) <= 4 = Z(Q_3) 
       
# Example where the minimum rank/maximum nullity was only recently found 
       
circ=graphs.CirculantGraph(9,[1,3]) show(circ) minrank_bounds(circ, all_bounds=True) 
       
({'diameter': 2,
  'forbidden minrank 2': 3,
  'rank': 0,
  'zero forcing': 4,
  'zero forcing fast': 4},
 {'clique cover': 12,
  'not outer planar': 6,
  'not path': 7,
  'not planar': 5,
  'order': 8,
  'rank': 9})
({'diameter': 2,
  'forbidden minrank 2': 3,
  'rank': 0,
  'zero forcing': 4,
  'zero forcing fast': 4},
 {'clique cover': 12,
  'not outer planar': 6,
  'not path': 7,
  'not planar': 5,
  'order': 8,
  'rank': 9})
# Here the best lower bound is 4 = 9 - 5 = |V(Circ)| - Z(Circ) and # the best upper bound is 5 = |V(Circ)| - 4 since Circ is not planar. # In other words, 4 <= M(Circ) <= 5 = Z(Circ) # # Tracy Hall has recently shown M(Circ(9,[1,3]) = 5 by constructing a matrix. # See the published sage file https://sage.math.iastate.edu/home/pub/128/ # Note that Z(Circ(9,[1,3]) = 5 also (clear from above, also explicity dislayed next. 
       
zero_forcing_set_bruteforce(circ) 
       
{0, 1, 2, 3, 4}
{0, 1, 2, 3, 4}
#################################### # Section 9.1: Standard zero forcing # There are two zero forcing set finders. # Wavefront is faster, but brute force allows you to favor one or more initial vertices, because it # it will return the minimum standard zero forcing set that is first lexicographically among such. # Examples of computing these functions are followed by examples that show the bounds on the effects of # graph operations on zero forcing number are tight. #################################### 
       
# Example ZF.1-1: Computing Z(G) - Half-graph example 
       
# Construct the sth half-graph def haf(s): ks=graphs.CompleteGraph(s) ks.relabel([1..s]) es=ks.complement() es.relabel([s+1..2*s+1]) hs=ks.union(es) for j in [1..s]: for k in [s+1..2*s+1-j]: hs.add_edge([j,k]) return hs 
       
h=haf(4) show(h) print zero_forcing_set_bruteforce(h) print zero_forcing_set_wavefront(h) 
       
{1, 2, 3, 4}
(4, [3, 4, 6, 7], 8)
{1, 2, 3, 4}
(4, [3, 4, 6, 7], 8)
# Example ZF.1-2: Graph on two prallel paths example 
       
p2p=graphs.PathGraph(5) p2p.relabel([1..5]) p=graphs.PathGraph(4) p.relabel([6..9]) p2p=p2p.union(p) p2p.add_edges([(1,7),(2,7),(3,7),(3,8),(4,9),(5,9)]) show(p2p) print Z(p2p) 
       
2
2
# One possibility for the two paths is (1,2,3,4,5) and (6,7,8,9). (1,2,3,4) and (6,7,8,9,5) is another 
       
# Examples for effects of deleting twins 
       
# Example ZF.1-3: Deleting an independent twin can maintain standard zero forcing number 
       
# The graph g in Figure 9.1 g=Graph({3:[1,2,4,5],4:[5,6],5:[7]}) show(g) print Z(g) 
       
2
2
g.delete_vertex(1) show(g) print Z(g) 
       
2
2
# Example ZF.1-4: Deleting an adjacent twin can reduce standard zero forcing number 
       
f=graphs.FriendshipGraph(4) show(f) print Z(f) 
       
5
5
f.delete_vertex(0) show(f) print Z(f) 
       
4
4
# Example ZF.1-5: Deleting an adjacent twin can maintain standard zero forcing number # Start with the next graph 
       
f.delete_vertex(1) show(f) print Z(f) 
       
3
3
f.delete_vertex(3) show(f) print Z(f) 
       
3
3
# Example ZF.1-6: Example for the maximum nullity product + 1 lower bound on zero forcing number of a Cartesian product (broom and complete graph) 
       
# parameters p=5 # broom path order s=4 # broom star order c=3 # complete graph order # build the graphs path = graphs.PathGraph(p) star = graphs.StarGraph(s) first=p-1 last=p+s ell=list([first..last]) star.relabel(ell) broom = path.union(star) b=broom.order() cg=graphs.CompleteGraph(c) cp=cg.cartesian_product(broom) cp.relabel() show(cp) # zero forcing zfsb=zero_forcing_set_wavefront(broom) zb=zfsb[0] zfscp=zero_forcing_set_wavefront(cp) zcp=zfscp[0] print 'r=', c, 'p=',p, 's=',s, 'n=', b print 'Z(K_r cartprod broom(p,s))=', zcp print 'Z(K_r)Z(broom)+1=', (c-1)* zb+1 print 'upper bound Z(K_r)*|broom|=',(c-1)*b print 'upper bound Z(broom)*|K_r|=',zb*c 
       
r= 3 p= 5 s= 4 n= 9
Z(K_r cartprod broom(p,s))= 9
Z(K_r)Z(broom)+1= 9
upper bound Z(K_r)*|broom|= 18
upper bound Z(broom)*|K_r|= 12
r= 3 p= 5 s= 4 n= 9
Z(K_r cartprod broom(p,s))= 9
Z(K_r)Z(broom)+1= 9
upper bound Z(K_r)*|broom|= 18
upper bound Z(broom)*|K_r|= 12
#################################### # Section 9.3: PSD zero forcing # Zplus is the PSD zero forcing number function. # These examples use Zplus to show the bounds for graph operations are tight. #################################### 
       
# Example ZF.3-1: Vertex deletion can lower PSD zero forcing number by 1 (independent twins is same as general) 
       
k25=graphs.CompleteBipartiteGraph(2,5) show(k25) Zplus(k25) 
       
2
2
g=k25.copy() g.delete_vertex(0) show(g) Zplus(g) 
       
1
1
# Example ZF.3-2: Deletion of an independent twin can maintain PSD zero forcing numbe9 
       
k25=graphs.CompleteBipartiteGraph(2,5) show(k25) Zplus(k25) 
       
2
2
g=k25.copy() g.delete_vertex(6) show(g) Zplus(g) 
       
2
2
# Example ZF.3-3: Deleting an edge can lower PSD zero forcing number by 1 
       
circ814=graphs.CirculantGraph(8,[1,4]) g=circ814.copy() show(g) Zplus(g) 
       
4
4
g=circ814.copy() g.delete_edge(0,4) show(g) Zplus(g) 
       
3
3
# Example ZF.3-4: Deleting an edge can raise PSD zero forcing number by 1 
       
circ814=graphs.CirculantGraph(8,[1,4]) g=circ814.copy() g.add_vertex(8) g.add_edge(8,2) show(g) Zplus(g) 
       
4
4
g.delete_edge(2,8) show(g) Zplus(g) 
       
5
5
# Example ZF.3-5: Contracting an edge can lower PSD zero forcing number by 1 
       
k5=graphs.CompleteGraph(5) g=k5.copy() show(g) Zplus(g) 
       
4
4
g.contract_edge(3,4) show(g) Zplus(g) 
       
3
3
#################################### # Section 9.4: Skew zero forcing # Zskew is the skew zero forcing number function. # Skew zero forcing number is computed for several graphs. # Maximum hollow rank is also illustrated. # Several examples use Zskew to show the bounds for edge deletion are tight. #################################### 
       
# Example ZF.4-1: Maximum hollow rank and maximum skew rank can be less than the order 
       
g=graphs.CompleteBipartiteGraph(1,5) show(g) m=g.adjacency_matrix() show(m) 
       

                                
                            

                                
# It is clear that the rank of any matrix in S_0(K_{1,5}) or S_-(K_{1,5}) is 2 < 6 = the order of K_{1,5} 
       
Zskew(g) 
       
4
4
# Example ZF.4-2: Compute Z_-(P) where P is the Petersen graph 
       
p=graphs.PetersenGraph() show(p) Zskew(p) 
       
4
4
# Example ZF.4-3: Compute Z_-(G_6) 
       
g6=Graph({3:[1,2,4],2:[1],4:[5,6],5:[6]}) show(g6) print find_loopedZ(g6,[]) Zskew(g6) 
       
1
1
1
1
# Example ZF.4-4: Deleting a leaf can leave skew zero forcing number unchanged (compare with Example ZF.4-3) 
       
g=Graph({3:[1,2,4,0],2:[1],4:[5,6],5:[6]}) show(g) Zskew(g) 
       
1
1
# Example ZF.4-5: Deleting an edge can raise skew zero forcing number by 2 
       
g=graphs.PathGraph(4) show(g) Zskew(g) 
       
0
0
g.delete_edge(0,1) show(g) Zskew(g) 
       
2
2
# Example ZF.4-6: Deleting an edge can lower skew zero forcing number by 2 
       
g=graphs.CycleGraph(4) show(g) Zskew(g) 
       
2
2
g.delete_edge(0,1) show(g) Zskew(g) 
       
0
0
# Example ZF.4-7: Z_-(P_4 \Box P_4) = M_-(P_4 \Box P_4) = M_0(P_4 \Box P_4) = 4 
       
p4=graphs.PathGraph(4) g=p4.cartesian_product(p4) g.relabel() show(g) Zskew(g) 
       
4
4
m4=p4.adjacency_matrix() eye=identity_matrix(4) m=m4.tensor_product(eye)-eye.tensor_product(m4) show(m) 4*4-m.rank() 
       
4
4
d=diagonal_matrix([1,-1,1,-1]) sm4=d*m4 sm=sm4.tensor_product(eye)-eye.tensor_product(sm4) show(sm) 4*4-sm.rank() 
       
4
4
# Example ZF.4-8: Skew forcing numbers of the half-graph and its complement 
       
h5=haf(5) print Zskew(h5) h5c=h5.complement() show(h5c) print Zskew(h5c) Zskew(h5)+Zskew(h5c) 
       
0
2
2
0
2
2
hc=haf(4) hc.add_vertices([9,10]) # make 9 a twin of 5 nbrs=hc.neighbors(5) eds=[] for i in nbrs: eds.append((9,i)) hc.add_edges(eds) show(hc) hc.is_isomorphic(h5c) 
       
True
True
#################################### # Section 9.7: Z_q # The function Zq is illustrated. #################################### 
       
# Example ZF.7-1: Computing Z_q(G) 
       
g=Graph({1:[3,4,5,6],2:[8,10,12],6:[7,8],8:[9],10:[11]}) show(g) 
       
print 'Zq(g,0)',Zq_compute(g,0),'Zplus(g)',Zplus(g) 
       
Zq(g,0) 1 Zplus(g) 1
Zq(g,0) 1 Zplus(g) 1
ordg=g.order() print 'Zq(g,n)',Zq_compute(g,ordg),'Z(g)',Z(g) 
       
Zq(g,n) 4 Z(g) 4
Zq(g,n) 4 Z(g) 4
Zq_compute(g,1) 
       
3
3
Zq_compute(g,2) 
       
4
4
#################################### # Section 9.8: Power Domination # minPowerDominatingSet(G) is a bruteforce function to produce a minimum power donimating set # by checking whether N[S] is a zero forcing set # PowerDom(G) is the function for power domination number #################################### 
       
# ZF.8-1 Example a non-induced forcing spider: generalized wheel GW(6,3) 
       
def gw(s,t): cs=graphs.CycleGraph(s) pt=graphs.PathGraph(t) g=pt.cartesian_product(cs) g.relabel([1..s*t]) g.add_vertex(0) for j in [1..s]: g.add_edge(0,j) return g gw63=gw(6,3) show(gw63) print PowerDom(gw63), minPowerDominatingSet(gw63) 
       
1 (0,)
1 (0,)
Z(gw63) 
       
6
6
# ZF.8-2 Example with sp(g) < pd(g) 
       
def y(s): ps=graphs.PathGraph(s) pt=graphs.PathGraph(2) g=ps.strong_product(pt) g.relabel([1..s*2]) g.add_vertex(0) g.add_edges([(0,1),(0,2)]) return g g7=y(7) show(g7) print PowerDom(g7), minPowerDominatingSet(g7) 
       
3 (0, 5, 11)
3 (0, 5, 11)
z=Z(g7) Del=g7.degree_sequence()[0] print 'Z(G) =',z,'Delta(G) =',Del,'ceiling(Z(G)/Delta(G)) =',ceil(n(z)/Del) 
       
Z(G) = 8 Delta(G) = 5 ceiling(Z(G)/Delta(G)) = 2
Z(G) = 8 Delta(G) = 5 ceiling(Z(G)/Delta(G)) = 2
# ZF.8-3: pd(G_e) = pd(G)+1 
       
g=Graph({1:[2,3,4,6],5:[4,10],6:[7,8,9],9:[4,10]}) show(g) PowerDom(g) 
       
2
2
g.subdivide_edge([4,9],1) show(g) PowerDom(g) 
       
3
3
#################################### # FUNCTIONS-HERE # These are the main function cells. Evaluate each one. #################################### 
       
# F-1 load main minimum rank/maximum nullity and zero forcing functions # zero forcing, PSD forcing, and minimum rank code # developed by S. Butler, L. DeLoss, J. Grout, H.T. Hall, J. LaGrange, J.C.-H. Lin,T. McKay, J. Smith, G. Tims # updated and maintained by Jephian C.-H. Lin URL='https://raw.githubusercontent.com/jephianlin/mr_JG/py2/' files=['Zq_c.pyx','Zq.py','zero_forcing_64.pyx','zero_forcing_wavefront.pyx','minrank.py', 'inertia.py'] for f in files: print("Loading %s..."%f); load(URL+f) 
       
Loading Zq_c.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/13518/tmp_6ACvK1.pyx..\
.
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/13518/tmp_5j0TJE.pyx..\
.
Loading zero_forcing_wavefront.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/13518/tmp_UR1s0V.pyx..\
.
Loading minrank.py...
Loading inertia.py...
Loading Zq_c.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/13518/tmp_6ACvK1.pyx...
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/13518/tmp_5j0TJE.pyx...
Loading zero_forcing_wavefront.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/13518/tmp_UR1s0V.pyx...
Loading minrank.py...
Loading inertia.py...
# F-2 additional function for zero forcing number using brute_force def Z(g): z=len(zero_forcing_set_bruteforce(g)) return z 
       
# F-3 main function cell zero forcing number loop graphs # skew forcing uses no loops # written by Jephian C.-H. Lin def gzerosgame(g,F=[],B=[]): """ Return the derived set for a given graph g with set of banned edges B and a initial set of vertices. The derived set is given by doing generalized zero forcing process. That is, if y is the only white neighbor of x and xy is not banned, then x could force y into black. Input: g: a simple graph F: a list of vertices of g B: a list of tuples representing banned edges of g Output: A set of black vertices when zero forcing process stops. Examples: sage: gzerosgame(graphs.PathGraph(5),[0]) set([0, 1, 2, 3, 4]) sage: gzerosgame(graphs.PathGraph(5),[0],[(1,2)]) set([0, 1]) """ S=set(F) # suspicuous vertices Black_vertices=set(F) # current black vertices again=1 # iterate again or not while again==1: again=0 for x in S: N=set(g.neighbors(x)) D=N.difference(Black_vertices) # set of white neighbors if len(D)==1: for v in D: y=v # the only white neighbor if (((x,y) in B)==False) and (((y,x) in B)==False): again=1 S.remove(x) S.add(y) Black_vertices.add(y) break return(Black_vertices) def gZ_leq(graph, support=[], bannedset=[],i=None): """ For a given graph with support and banned set, if there is a zero forcing set of size i then return it; otherwise return False. Input: graph: a simple graph support: a list of vertices of g bannedset: a list of tuples representing banned edges of graph i: an integer, the function check gZ <= i or not Output: if F is a zero forcing set of size i and support is a subset of F, then return F False otherwise Examples: sage: gZ_leq(graphs.PathGraph(5),[],[],1) set([0]) sage: gZ_leq(graphs.PathGraph(5),[],[(0,1)],1) False """ if i < len(support): # print 'i cannot less than the cardinality of support' return False j=i-len(support) # additional number of black vertices VX=graph.vertices() order=graph.order() for y in support: VX.remove(y) # VX is the vertices outside support now for subset in Subsets(VX,j): test_set=set(support).union(subset) # the set is tested to be a zero forcing set outcome=gzerosgame(graph, test_set, bannedset) if len(outcome)==order: return test_set return False def find_gzfs(graph, support=[], bannedset=[], upper_bound=None, lower_bound=None): """ For a given graph with support and banned set, return the an optimal generalized zero forcing set. If upper_bound is less than the generalized zero forcing number then return ['wrong']. If lower_bound is greater than the generalized zero forcing number then the return value will not be correct Input: graph: a simple graph support: a list of vertices of g bannedset: a list of tuples representing banned edges of graph upper_bound: an integer supposed to be an upper bound of gZ. lower_bound: an integer supposed to be a lower bound of gZ. The two bounds may shorten the computation time. But one may leave it as default value if one is not sure. Output: if F is an optimal zero forcing set of size i then return F. If upper_bound is less than the general zero forcing number then return ['wrong']. Examples: sage: find_gzfs(graphs.PathGraph(5)) set([0]) sage: find_gzfs(graphs.PathGraph(5),[1],[(3,2)]) set([0, 1, 3]) """ VX=graph.vertices() order=graph.order() s=len(support) for y in support: VX.remove(y) # VX is the vertices outside support now if upper_bound==None: upper_bound=order # the default upper bound if lower_bound==None: lower_bound=len(VX) # temporary lower bound for v in VX: N=set(graph.neighbors(v)) D=N.difference(support) lower_bound=min([lower_bound,len(D)]) for v in support: N=set(graph.neighbors(v)) D=N.difference(support) lower_bound=min([lower_bound,len(D)-1]) lower_bound=lower_bound+s # the default lower bound i=upper_bound find=1 # does sage find a zero forcing set of size i outcome=['wrong'] # default outcome while i>=lower_bound and find==1: find=0 leq=gZ_leq(graph, support, bannedset,i) # check gZ <= i or not if leq!=False: outcome=leq find=1 i=i-1 return outcome def find_gZ(graph, support=[], bannedset=[], upper_bound=None, lower_bound=None): """ For a given graph with support and banned set, return the zero. upper_bound and lower_bound could be left as default value if one is not sure. Input: graph: a simple graph support: a list of vertices of g bannedset: a list of tuples representing banned edges of graph upper_bound: an integer supposed to be an upper bound of gZ. lower_bound: an integer supposed to be a lower bound of gZ. The two bounds may shorten the computation time. But one may leave it as default value if one is not sure. Output: the generalized zero forcing number Examples: sage: find_gZ(graphs.PathGraph(5)) 1 sage: find_gZ(graphs.PathGraph(5),[1],[(3,2)]) 3 """ return len(find_gzfs(graph, support, bannedset, upper_bound, lower_bound)) def X(g): """ For a given graph g, return the verices set X of a part of the bipartite used to compute the exhaustive zero forcing number. Input: g: a simple graph Output: a list of tuples ('a',i) for all vertices i of g Examples: sage: X(graphs.PathGraph(5)) [('a', 0), ('a', 1), ('a', 2), ('a', 3), ('a', 4)] """ return [('a',i) for i in g.vertices()] def Y(g): """ For a given graph g, return the verices set Y of the other part of the bipartite used to compute the exhaustive zero forcing number. Input: g: a simple graph Output: a list of tuples ('b',i) for all vertices i of g Examples: sage: Y(graphs.PathGraph(5)) [('b', 0), ('b', 1), ('b', 2), ('b', 3), ('b', 4)] """ return [('b',i) for i in g.vertices()] def tilde_bipartite(g,I=[]): """ For a given graph g and an index set I, return the bipartite graph \widetilde{G}_I used to compute the exhaustive zero forcing number. Input: g: a simple graph I: a list of vertices of g Output: the bipartite graph \widetilde{G}_I Examples: sage: h=tilde_bipartite(graphs.PathGraph(5),[1]) sage: h.vertices() [('a', 0), ('a', 1), ('a', 2), ('a', 3), ('a', 4), ('b', 0), ('b', 1), ('b', 2), ('b', 3), ('b', 4)] sage: h.edges() [(('a', 0), ('b', 1), None), (('a', 1), ('b', 0), None), (('a', 1), ('b', 1), None), (('a', 1), ('b', 2), None), (('a', 2), ('b', 1), None), (('a', 2), ('b', 3), None), (('a', 3), ('b', 2), None), (('a', 3), ('b', 4), None), (('a', 4), ('b', 3), None)] """ E0=[(('a',i), ('b',i)) for i in I] # edges given by I E1=[] # invariant edges for i in g.vertices(): for j in g.neighbors(i): E1.append((('a',i),('b',j))) h=Graph() h.add_vertices(X(g)) h.add_vertices(Y(g)) h.add_edges(E0) h.add_edges(E1) # h=(X union Y, E0 union E1) return h def find_EZ(g,bound=None): """ For a given graph g, return the exhaustive zero forcing number of g. A given bound may shorten the computation. Input: g: a simple graph bound: a integer as an upper bound. It could be left as default value if one is not sure. Output: the exhaustive zero forcing number (EZ) of g Examples: sage: find_EZ(graphs.PathGraph(5)) 1 sage: h=graphs.CycleGraph(5) sage: h.add_vertices([5,6,7,8,9]) sage: h.add_edges([(0,5),(1,6),(2,7),(3,8),(4,9)]) sage: find_EZ(h) # the EZ of a 5-sun 2 """ order=g.order() Z=find_gZ(g) # without support and banned set, the value is the original zero forcing number if bound==None: bound=Z # default upper bound gZ_bound=bound+order V=set(g.vertices()) e=-1 # temporary output for I in Subsets(V): leq=gZ_leq(tilde_bipartite(g,I),Y(g),[],e) # this avoid abundant computation if leq==False: e=find_gZ(tilde_bipartite(g,I),Y(g),[],gZ_bound,e+1) # in this case, we already know e+1-order<=gZ-order<=bound and so e+1<=gZ<=gZ_bound if e==gZ_bound: break return e-order # EZ=max-order def find_loopedZ(g,I): """ For a given graph g and the index of the vertices with loops, return the zero forcing number of this looped graph. Input: g: a simple graph, the underlying graph of the looped graph. I: the index of the vertices with loops. Output: the zero forcing number of this looped graph. Examples: sage: g = Graph({0:[1],1:[0]}); sage: I=[0,1]; sage: find_loopedZ(g,I) 1 sage: g = Graph({0:[1],1:[0]}); sage: I=[0]; sage: find_loopedZ(g,I) 0 """ return find_gZ(tilde_bipartite(g,I),Y(g),[])-g.order() def Zskew(g): # report Z_-(g) return find_loopedZ(g,[]) 
       
# F-4 Power domination functions # by Brian Wissman # input: a graph G and a subset of its vertices V # output: true/false depending if V is a power dominating set of G def isPowerDominatingSet(G,V): N=[] for i in V: N+=G.neighbors(i) NVert=uniq(N+list(V)) A=zerosgame(G,NVert) if len(A)==G.order(): return True else: return False # input: a graph G # output: a power dominating set of G that achieves the power domination number def minPowerDominatingSet(G): V = G.vertices() for i in range(1,len(V)+1): S = subsets(V,i) for s in S: if isPowerDominatingSet(G,s): return s # input: a graph G # output: the power domination number of G def PowerDom(G): V = G.vertices() for i in range(1,len(V)+1): S = subsets(V,i) for s in S: if isPowerDominatingSet(G,s): p=len(s) return p