Macaulay2 » Documentation
Packages » EdgeIdeals :: numTriangles
next | previous | forward | backward | up | index | toc

numTriangles -- returns the number of triangles in a graph

Synopsis

Description

This method is based on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the square of the Alexander dual of the edge ideal. The algorithm counts the number of these associated primes of height 3.

See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd holes in a graph." (2008) Preprint. arXiv:0806.1159v1.

i1 : R = QQ[x_1..x_6];
 
i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5-cycle and a triangle

o2 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
                         1   2     2   3     3   4     1   5     4   5     1   6     5   6
           "ring" => R
           "vertices" => {x , x , x , x , x , x }
                           1   2   3   4   5   6

o2 : Graph
 
i3 : numTriangles G

o3 = 1
 
i4 : H = completeGraph R;
 
i5 : numTriangles H == binomial(6,3)

o5 = true

See also

Ways to use numTriangles:

For the programmer

The object numTriangles is a method function.