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

# numTriangles -- returns the number of triangles in a graph

- Usage:
    `d = numTriangles G`
- Inputs:
  - G, a graph,
- Outputs:
  - d, an integer, the number of triangles contained in G

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

- allOddHoles -- returns all odd holes in a graph
- getCliques -- returns cliques in a graph

## Ways to use numTriangles:

- `numTriangles(Graph)`

## For the programmer

The object numTriangles is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/EdgeIdeals.m2:3807:0.