Triangle k Core

Triangle k Core

The triangle k core, or k truss have been intoduced by Cohen and Zhang and Parthasarathy independently and runs in ${𝒪}(\mathrm{\Delta }(G)m)$ time, where $\mathrm{\Delta }(G)$ is the maximum degree and $m$ the number of edges.

Definition Triangle Core

The triangle k-core of a simple undirected graph $G=(V,E)$ is the inclusion maximal subgraph $C_k(G)\subset G$ where each edge $e\in E(C_k(G))$ is part of at least $k$ triangles in $C_k(G)$.

More detailed background information is provided in

Definition Triangle Core Number

The triangle core number of an edge $e\in E(G)$ is the maximal k such that $e\in C_k(G)$