Bounds and algorithms for graph trusses

Paul Burkhardt, Vance Faber, David G. Harris

The $k$-truss, introduced by Cohen (2005), is a graph where every edge is incident to at least $k$ triangles. This is a relaxation of the clique. It has proved to be a useful tool…