SM-3e-TestingForClaws

4144 days ago by MathFest

Knowing that if a graph is clawfree then its independence polynomial is logarithmically concave, our next goal is to develop an algorithm for testing whether or not a given graph is indeed clawfree. We do this here, beginning with a couple of simple methods to perform nuts-and-bolts computations on the vertices of an input graph. Respectively, the following functions extract subsets of a given size from a given superset and determine the neighborhood of a given vertex in a given graph, when input the graph's adjacency matrix:
def subset_size_n(L,n): pow = list(powerset(L)) sets = [] for s in pow: if len(s) == n: sets.append(s) return sets def neighborhood(m,i): nbhd = [] for j in [0..len(m.rows())-1]: if m.rows()[i][j] == 1: nbhd.append(j) return nbhd 
       
Now to actually test for claws (naively!). We divide the work between two simple methods; the first tests whether a given trio of vertices might form the leaves of a claw; the second (which calls the first over and over) runs through all potential centers for claws. If ever we find a claw, we stop the search and declare the presence of such a claw; otherwise we terminate and indicate that the graph is clawfree.
def test_claw_leaves(m,i,j,k): return m.rows()[i][j] == 0 and m.rows()[j][k] == 0 and m.rows()[k][i] == 0 def test_claw_free(m): for i in [0..len(m.rows())-1]: pot_leaves = subset_size_n(neighborhood(m,i),3) for s in pot_leaves: if test_claw_leaves(m,s[0],s[1],s[2]) == True: return False return True 
       
Let's try it out:
m = matrix(graphs.RandomTreePowerlaw(15)) test_claw_free(m) 
       
See how easy? Of course, nearly any tree we generate is going to have a claw in it, so let's try the algorithm out on something we know is clawfree, like a cycle:
m = matrix(graphs.CycleGraph(5)) test_claw_free(m)