Minimum Rank, Zero Forcing, Power Domination

1546 days ago by hogben

# This file demonstrates software for computing minimum rank bounds, including # zero forcing number and some variants of zero forcing number, and power domination. # You must evaluate the next two cells first. # For issues contact hogben@aimath.org and jephianlin@gmail.com 
       
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/14724/tmp_NRYqbn.pyx..\
.
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/14724/tmp_Z0QtBB.pyx..\
.
Loading zero_forcing_wavefront.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/14724/tmp_LpvTtC.pyx..\
.
Loading minrank.py...
Loading inertia.py...
Loading Zq_c.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/14724/tmp_NRYqbn.pyx...
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/14724/tmp_Z0QtBB.pyx...
Loading zero_forcing_wavefront.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/14724/tmp_LpvTtC.pyx...
Loading minrank.py...
Loading inertia.py...
# input: a graph G and a subset of its vertices V # ouput: 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 
       
# the rest of this file illustrates the use of this software 
       
# graphs 
       
g=Graph({1:[3,4,5,6],2:[8,10,12],6:[7,8],8:[9],10:[11]}) show(g) 
       
c=graphs.CycleGraph(5) p=graphs.PathGraph(3) cp=p.cartesian_product(c) cp.relabel() show(cp) 
       
b=graphs.CompleteBipartiteGraph(5,3) show(b) 
       
c=graphs.CirculantGraph(9,[1,3]) show(c) 
       
# zero forcing 
       
# there are two zero forcing set finders # wavefront is faster but brite force allows you to favor initial vertices # (if 0 can be in a min zero forcing set it wil be in the one returned) 
       
zero_forcing_set_wavefront(cp) 
       
(5, [5, 10, 11, 12, 13], 26)
(5, [5, 10, 11, 12, 13], 26)
zero_forcing_set_bruteforce(cp) 
       
{0, 1, 2, 3, 4}
{0, 1, 2, 3, 4}
# so Z(cp)=5, where Z(G) is zero forcing number of G 
       
# Zplus is postive semdifinite zero forcing number 
       
Zplus(cp) 
       
5
5
zero_forcing_set_wavefront(g) 
       
(4, [3, 4, 6, 10], 52)
(4, [3, 4, 6, 10], 52)
Zplus(g) 
       
1
1
zero_forcing_set_wavefront(b) 
       
(6, [0, 2, 3, 4, 6, 7], 29)
(6, [0, 2, 3, 4, 6, 7], 29)
Zplus(b) 
       
3
3
zero_forcing_set_wavefront(c) 
       
(5, [2, 3, 4, 6, 8], 10)
(5, [2, 3, 4, 6, 8], 10)
# minimum rank bounds # this program implements various known bounds and cut vertex reduction # it returns (lower bound, upper bound) # if these ae equal you have the minimum rank 
       
minrank_bounds(g) 
       
(8, 8)
(8, 8)
# so mr(g)=8 
       
minrank_bounds(b) 
       
(2, 2)
(2, 2)
# so mr(g)=2 
       
minrank_bounds(c) 
       
(4, 5)
(4, 5)
# so 4 <= mr(c) <= 5 
       
# The software does not always find the known results as in the next example. # It is known that mr(cp) = 10 [AIM Minimum Rank - Special Graphs Work Group, # Zero forcing sets and the minimum rank of graphs. Lin. Alg. Appl., 428: 1628--1648, 2008]. 
       
minrank_bounds(cp) 
       
(10, 12)
(10, 12)
minrank_bounds(cp, all_bounds=True) 
       
({'diameter': 4,
  'forbidden minrank 2': 3,
  'rank': 0,
  'zero forcing': 10,
  'zero forcing fast': 10},
 {'clique cover': 25,
  'not outer planar': 12,
  'not path': 13,
  'order': 14,
  'rank': 15})
({'diameter': 4,
  'forbidden minrank 2': 3,
  'rank': 0,
  'zero forcing': 10,
  'zero forcing fast': 10},
 {'clique cover': 25,
  'not outer planar': 12,
  'not path': 13,
  'order': 14,
  'rank': 15})
# power domination 
       
minPowerDominatingSet(g) 
       
(1, 2)
(1, 2)
isPowerDominatingSet(g,[1,2]) 
       
True
True
PowerDom(g) 
       
2
2
minPowerDominatingSet(cp) 
       
(0, 2)
(0, 2)
PowerDom(g) 
       
2
2