2
$\begingroup$

I have read David Eppstein's paper about maximal clique enumeration by using degeneracy order. It has mentioned the core decomposition, which is removing the vertex with the smallest degree iteratively.

And I pick up with a theorem:
If we remove the vertex with the smallest degree iteratively until the smallest degree is |S|-1, where S is the remaining graph, is S a maximal clique?

example graph:

example graph

In this graph, we will delete vertex a whose degree is the smallest one ( deg(a)=2 ), and then delete vertex f. And we will get the 4-maximal clique {b,c,d,e}.

I cannot prove this theorem but I also can't find a counterexample. Is there anyone can help me figure out this theorem right or wrong?

PS:

Clique is a subgraph whose every vertex is adjacent to each other. And maximal clique is a clique that cannot be contained by another clique, it means the maximal one cannot be extended.

I can prove the remaining graph that above algorithm produced is not a maximum clique which is the largest one in the graph, but I can't prove this graph whether is a maximal clique.

Also notice that when the vertex v is removed from the graph, all it's neighbors' degree will decrease one.

Improve this question
$\endgroup$
3
$\begingroup$

No. The illustration shows a graph (the graph of a cube with one corner truncated) and a valid removal sequence such that the vertices left at the point when the minimum degree equals $|S|-1$ (the two red vertices) do not form a maximal clique.

enter image description here

In this example, some other valid removal orderings could still produce a maximal clique. Probably there are more elaborate versions of this example that force the remaining clique to be non-maximal for all valid removal orderings.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you, David, I have read your two papers about MCE and I don't know that you were here. This counterexample is enough to my question. Thank you again. $\endgroup$
    – Yinuo
    Jan 3 '18 at 8:35
  • $\begingroup$ How about adding a vertex to each edge of the Peterson graph. The new vertex is adjacent to both ends of the edge, and hence has degree two. The decomposition will remove all new vertices first, and then it ends with an edge. $\endgroup$
    – Yixin Cao
    Jan 6 '18 at 7:07
  • $\begingroup$ You mean, keeping the existing edge but adding a new degree-two vertex adjacent to its endpoints? That should work with any triangle-free cubic graph (e.g. $K_{3,3}$); using Petersen is overkill. $\endgroup$
    – David Eppstein
    Jan 6 '18 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.