1
$\begingroup$

Cross-posted on Operations Research SE.

I'm trying to understand K-Truss Graphs which are defined as such

The k-truss is a subset of the graph with the same number of vertices, where each edge appears in at least $𝑘 − 2$ triangles in the original graph.

Given this example:

Example

The $4$-Truss should be $2-1-4$ since we want edges present in at least $2$ triangles of the original graph:

  • edge $1-2$ is present in triangle $0-1-2$ and triangle $1-2-4.$
  • edge $1-4$ is present in triangle $1-3-4$ and triangle $1-2-4.$

Is it correct?

$\endgroup$
2
  • $\begingroup$ Ummm... what is your question? $\endgroup$ Commented Aug 18, 2021 at 23:05
  • $\begingroup$ I'm wondering if my solution on the given example matches the definition and its properties $\endgroup$
    – karalis1
    Commented Aug 18, 2021 at 23:08

1 Answer 1

1
$\begingroup$

Your solution is consistent with the definition you gave. But note that the $k$-truss of a graph $G = (V,E)$ is usually defined as the maximal subgraph $H = (V',E')$ such that every edge of $H$ is in at least $k-2$ triangles within $H$ (not in the original graph). According to this definition, the $4$-truss of your example graph is empty.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, that's the reason why the algorithm I implemented from a pseudocode gave me a different output from what I expected at the end of the iterations, it was an empty matrix as you said...At this point if I'm not misunderstanding again, the 3-truss graph should be the original graph itself? $\endgroup$
    – karalis1
    Commented Aug 19, 2021 at 14:53
  • 1
    $\begingroup$ Yes! The $3$-truss is just the union of the triangles in the graph; in this case, the whole graph. $\endgroup$
    – Dániel G.
    Commented Aug 19, 2021 at 15:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .