[d,S] = dom(g) --- domination number of g The domination number is the smallest size of a set of vertices S with the property that every vertex is either in S or else distance 1 from some vertex in S. Returns d, the domination number, and S a smallest dominating set. WARNING: It is NP hard to find the domination number of a graph, so this will work slowly (if at all) for large graphs. REQUIRES THE OPTIMIZATION TOOLBOX
0001 function [d,S] = dom(g) 0002 % [d,S] = dom(g) --- domination number of g 0003 % The domination number is the smallest size of a set of vertices S with 0004 % the property that every vertex is either in S or else distance 1 from 0005 % some vertex in S. 0006 % Returns d, the domination number, and S a smallest dominating set. 0007 % WARNING: It is NP hard to find the domination number of a graph, so this 0008 % will work slowly (if at all) for large graphs. 0009 % 0010 % REQUIRES THE OPTIMIZATION TOOLBOX 0011 0012 n = nv(g); 0013 A = matrix(g) + eye(n); 0014 f = ones(1,n); 0015 b = ones(n,1); 0016 [x,d] = bintprog(f,-A,-b); 0017 S = find(x);