HHLSSZ-extPSDproptime

831 days ago by hogben

# 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