NG_powerdomination

2182 days ago by hogben

########################### # This file contains computations supporting the paper # Note on Nordhaus-Gaddum problems for power domination # by Katherine F. Benson, Daniela Ferrero, Mary Flagg, # Veronika Furst, Leslie Hogben, and Violeta Vasilevska ########################### 
       
########################### # Zero forcing code is from the Miminim Rank library (Jason Groute et al.) # Power domination code written by Brian Wissman # Calling code written by Leslie Hogben ########################### 
       
########################### # This file shows that for graphs g on <= 11 vertices such that minimum degree of # both g and its complement g^c are at least 4, # pd(g)+pd(g^c) <= floor(n/3)+2. # It is proved in the paper that if minimum degree g or g^c <=3, # then pd(g)+pd(g^c) <= floor(n/3)+2 # # This file also verifies examples of orders 8 and 11 that attain # pd(g)+pd(g^c) = floor(n/3)+2. ########################### 
       
########################### # necessary initial code ########################### 
       
URL='https://raw.githubusercontent.com/jephianlin/mr_JG/master/' files=['Zq_c.pyx','Zq.py','zero_forcing_64.pyx','zero_forcing_wavefront.pyx','minrank.py', 'inertia.py'] for f in files: load(URL+f) 
       
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/25739/tmp_8LoIo2.pyx..\
.
/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/repl/lo\
ad.py:251: DeprecationWarning: the file "stdsage.pxi" is deprecated,
cimport the functions that you need
See http://trac.sagemath.org/23855 for details.
  exec(load_cython(fpath), globals)
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/25739/tmp_ArJf7Z.pyx..\
.
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/25739/tmp_Q0vpkV.pyx..\
.
warning:
_home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0\
.pyx:110:18: Non-trivial type declarators in shared declaration (e.g.
mix of pointers and values). Each pointer declaration should be on its
own line.
warning:
_home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0\
.pyx:110:32: Non-trivial type declarators in shared declaration (e.g.
mix of pointers and values). Each pointer declaration should be on its
own line.
warning:
_home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0\
.pyx:110:47: Non-trivial type declarators in shared declaration (e.g.
mix of pointers and values). Each pointer declaration should be on its
own line.
warning:
_home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0\
.pyx:110:73: Non-trivial type declarators in shared declaration (e.g.
mix of pointers and values). Each pointer declaration should be on its
own line.
/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/repl/lo\
ad.py:251: DeprecationWarning: the file "cdefs.pxi" is deprecated,
cimport the functions that you need
See http://trac.sagemath.org/23855 for details.
  exec(load_cython(fpath), globals)
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/25739/tmp_8LoIo2.pyx...
/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/repl/load.py:251: DeprecationWarning: the file "stdsage.pxi" is deprecated, cimport the functions that you need
See http://trac.sagemath.org/23855 for details.
  exec(load_cython(fpath), globals)
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/25739/tmp_ArJf7Z.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/25739/tmp_Q0vpkV.pyx...
warning: _home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0.pyx:110:18: Non-trivial type declarators in shared declaration (e.g. mix of pointers and values). Each pointer declaration should be on its own line.
warning: _home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0.pyx:110:32: Non-trivial type declarators in shared declaration (e.g. mix of pointers and values). Each pointer declaration should be on its own line.
warning: _home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0.pyx:110:47: Non-trivial type declarators in shared declaration (e.g. mix of pointers and values). Each pointer declaration should be on its own line.
warning: _home_sageuser_3__sage_temp_sage_math_iastate_edu_25739_tmp_Q0vpkV_pyx_0.pyx:110:73: Non-trivial type declarators in shared declaration (e.g. mix of pointers and values). Each pointer declaration should be on its own line.
/home/sage/build/sage-8.1/local/lib/python2.7/site-packages/sage/repl/load.py:251: DeprecationWarning: the file "cdefs.pxi" is deprecated, cimport the functions that you need
See http://trac.sagemath.org/23855 for details.
  exec(load_cython(fpath), globals)
# 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 
       
want={}; 
       
########################### # Data: we display everything with pd(g)+pd(gc) >= floor(n/e)+2 ########################### 
       
########################### # n=9 ########################### 
       
### Code that obtains the data for graphs with large NGsum for power domination n=9 n=9 m=n*(n-1)/2 half_m=ceil(m/2) want[n]=[]; counter=0; B=floor(n/3)+1; print n, " ", B for g in graphs.nauty_geng("%s %s:%s "%(n,0,half_m)): counter+=1; gc=g.complement(); d=min(g.degree_sequence()) dc=min(gc.degree_sequence()) if (d>3) and (dc>3): # to go over n/3+2 must have d, dc >3 pdG=PowerDom(g); pdGc=PowerDom(gc); if pdG+pdGc>B: print n," ",B," ",pdG+pdGc, " ", pdG, " ", pdGc, g.canonical_label().graph6_string() want[n].append(g.canonical_label().graph6_string()); print n, [len(want[n]),counter],N(len(want[n])/counter,digits=2); 
       
9   4
9 [0, 154354] 0.00
9   4
9 [0, 154354] 0.00
# so none > n/3+2 
       
########################### # n=10 ########################### 
       
### Code that obtains the data for graphs with large NGsum for power domination n=10 n=10 m=n*(n-1)/2 half_m=ceil(m/2) want[n]=[]; counter=0; B=floor(n/3)+1; print n, " ", B for g in graphs.nauty_geng("%s %s:%s "%(n,0,half_m)): counter+=1; gc=g.complement(); d=min(g.degree_sequence()) dc=min(gc.degree_sequence()) if (d>3) and (dc>3): # to go over n/3+1 must have d, dc >3 pdG=PowerDom(g); pdGc=PowerDom(gc); if pdG+pdGc>B: print n," ",B," ",pdG+pdGc, " ", pdG, " ", pdGc, g.canonical_label().graph6_string() want[n].append(g.canonical_label().graph6_string()); print n, [len(want[n]),counter],N(len(want[n])/counter,digits=2); 
       
10   4
10 [0, 7361436] 0.00
10   4
10 [0, 7361436] 0.00
# so none greater than floor(n/3)+2 
       
########################### # n=11 ########################### 
       
### Code that obtains the data for graphs with large NGsum for power domination n=11 n=11 m=n*(n-1)/2 half_m=ceil(m/2) want[n]=[]; counter=0; B=floor(n/3)+1; print n, " ", B for g in graphs.nauty_geng("%s %s:%s "%(n,0,half_m)): counter+=1; gc=g.complement(); d=min(g.degree_sequence()) dc=min(gc.degree_sequence()) diam=g.diameter() diamc=gc.diameter() if (d>3) and (dc>3) and (diam==2) and (diamc==2): # to go over n/3+2 must have d, dc >3, diam=diamc=2 pdG=PowerDom(g); pdGc=PowerDom(gc); if pdG+pdGc>B: print n," ",B+1," ",pdG+pdGc, " ", pdG, " ", pdGc, g.canonical_label().graph6_string() want[n].append(g.canonical_label().graph6_string()); print n, [len(want[n]),counter],N(len(want[n])/counter,digits=2); 
       
11   4
11 [0, 615820560] 0.00
11   4
11 [0, 615820560] 0.00
# so none greater than floor(n/3)+2 
       
########################### # order 8 example with # pd(g)+pd(g^c) = floor(n/3)+2 ########################### 
       
p4=graphs.PathGraph(4) p2=graphs.PathGraph(2) g=p2.strong_product(p4) g.relabel() show(g) minPowerDominatingSet(g) 
       
(0, 2)
(0, 2)
gc=g.complement() show(gc) minPowerDominatingSet(gc) 
       
(0, 1)
(0, 1)
########################### # order 11 example with # pd(g)+pd(g^c) = floor(n/3)+2 ########################### 
       
g=Graph({1:[4,5,6,9,10,11],2:[4,5,6],3:[4,5,6],7:[9,10,11],8:[9,10,11]}) show(g) minPowerDominatingSet(g) 
       
(1, 2, 7)
(1, 2, 7)
gc=g.complement() show(gc) minPowerDominatingSet(gc) 
       
(1, 4)
(1, 4)