# Computations supporting
# Upper bounds for positive semidefinite propagation time
# by Hogben, Hunnell, Liu, Scheurger, Small, Zhang
#
# Enter each cell in order
|
|
# Utilities
#
# Load PSD propagation time funtions, including pt_plus(G,S) = PSD propagation time of a set S
# code by Nathan Warnberg
# updated and maintained by Jephian C.-H. Lin
load('https://raw.githubusercontent.com/jephianlin/zero_forcing/master/psd_prop_time_interval.py')
#
# Function to compute pt_+(G,k) = minimum PSD propagation time over sets of size k
# input: a graph G and a positive integer k
# ouput: pt_+(G,k)
def ptpk(G,k):
ord=G.order()
V = G.vertices()
S = subsets(V,k)
ptp = -1
for s in S:
ptps=pt_plus(G,s)
if (ptp < 0):
ptp=ptps
if (ptps >= 0) and (ptps < ptp):
ptp=ptps
return ptp
xrange test passed Loading Zq_c.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/25469/tmp_djJUdr.pyx..\ . Loading Zq.py... Loading zero_forcing_64.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/25469/tmp_FaLyBZ.pyx..\ . Loading zero_forcing_wavefront.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/25469/tmp_AaLFEi.pyx..\ . Loading minrank.py... Loading inertia.py... xrange test passed Loading Zq_c.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/25469/tmp_djJUdr.pyx... Loading Zq.py... Loading zero_forcing_64.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/25469/tmp_FaLyBZ.pyx... Loading zero_forcing_wavefront.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/25469/tmp_AaLFEi.pyx... Loading minrank.py... Loading inertia.py... |
# Computations for Theorem 4.5
|
|
# define graph labels as in proof
x=var('x')
y=var('y')
z=var('z')
xp=var('xp')
yp=var('yp')
zp=var('zp')
a0=var('a0')
b0=var('b0')
a1=var('a1')
b1=var('b1')
a2=var('a2')
b2=var('b2')
|
|
h8=Graph({y:[z,x,yp,xp,b0],yp:[zp,xp,x,a0],x:[a0,z],xp:[b0,zp],z:[zp]},format='dict_of_lists')
show(h8)
print Zplus(h8),ptpk(h8,3)
3 3 3 3 
|
h8c=h8.complement()
h8c.is_isomorphic(h8)
True True |
h10=Graph({y:[z,x,yp,xp,b0],yp:[zp,xp,x,a0],x:[a0,z],xp:[b0,zp],z:[zp],a1:[a0], b1:[b0]},format='dict_of_lists')
show(h10)
h10c=h10.complement()
print Zplus(h10c), ptpk(h10c,5)
5 3 5 3 
|
h12=Graph({y:[z,x,yp,xp,b0],yp:[zp,xp,x,a0],x:[a0,z],xp:[b0,zp],z:[zp],a1:[a0,a2], b1:[b0,b2]},format='dict_of_lists')
show(h12)
h12c=h12.complement()
print Zplus(h12c), ptpk(h12c,7)
7 3 7 3 
|