# 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 |
|
|