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