Minimum Rank - Zero Forcing

1436 days ago by hogben

# This file demonstrates software for computing minimum rank bounds, including # zero forcing number, and variants of zero forcing number. # You must evaluate the next cell first. # For issues contact hogben@aimath.org, jephianlin@gmail.com, butler@iastate.edu 
       
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/1/.sage/temp/sage.math.iastate.edu/14513/tmp_IsleL2.pyx..\
.
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling
/home/sageuser/1/.sage/temp/sage.math.iastate.edu/14513/tmp_7Q99fP.pyx..\
.
Loading zero_forcing_wavefront.pyx...
Compiling
/home/sageuser/1/.sage/temp/sage.math.iastate.edu/14513/tmp_qY0kTf.pyx..\
.
Loading minrank.py...
Loading inertia.py...
Loading Zq_c.pyx...
Compiling /home/sageuser/1/.sage/temp/sage.math.iastate.edu/14513/tmp_IsleL2.pyx...
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling /home/sageuser/1/.sage/temp/sage.math.iastate.edu/14513/tmp_7Q99fP.pyx...
Loading zero_forcing_wavefront.pyx...
Compiling /home/sageuser/1/.sage/temp/sage.math.iastate.edu/14513/tmp_qY0kTf.pyx...
Loading minrank.py...
Loading inertia.py...
# 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) 
       
# 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
# minimum rank bounds # this program implements various known bounds and cut vertex reduction 
       
minrank_bounds(g) 
       
(8, 8)
(8, 8)
minrank_bounds(b) 
       
(2, 2)
(2, 2)
# 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})