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