Let $\mathrm{M}\in\lbrace0,1\rbrace^n$ be the adjacency matrix of a graph $\mathrm{G}\left(V,E\subseteq\lbrace\lbrace u,v\rbrace| u,v\in V\rbrace\right)$ of order $n$.

Let $\mathrm{G}$ additionally be metric in the sense, that $$\lbrace v_i, v_j, v_k\rbrace\subseteq V\ \ \wedge\ \ w_{uv}\in\lbrace 0,1\rbrace\ \ \wedge\ \ w_{uv}=1\iff e_{uv}\in E$$ $$\implies w_{ij}+w_{jk}+w_{ki}\ \in\ \lbrace 0,2,3\rbrace$$

Question: is it then true that $$\mathrm{rank}(\mathrm{M})=\max_{n'}\mathrm{K}_{n'}\subseteq\mathrm{G}$$ resp. how is the the rank of the adjacency matrix related to the size of the maximal clique?

  • $\begingroup$ For triangle free graphs the adjacency matrix may easily have large rank. Say, consider the long cycle. $\endgroup$ – Fedor Petrov Dec 20 '18 at 8:56
  • $\begingroup$ @FedorPetrov shame on me; I will have to edit my question to make it non-trivial. $\endgroup$ – Manfred Weis Dec 20 '18 at 9:21

I also assume that the graph contains at least one edge, else the maximal clique contains 1 vertex while the rank is 0. In any graph (not necessarily metric) which contains at least one edge the rank of the adjacency matrix is not less than the size of maximal clique (look to corresponding minor).

Your metric condition is equivalent to the following: the vertices may be partitioned onto $m$ disjoint non-empty groups $V_1,\dots,V_m$ so that any two vertices from the same $V_i$ are not joined while any two vertices from different $V_i$'s are joined. It implies that the rank of such a matrix is at most $m$, since there are exactly $m$ different rows. On the other hand, the maximal clique size is exactly $m$. Therefore here we have indeed the equality.

  • $\begingroup$ So the NP-complete decision problem of whether a graph contains a clique larger than a given size is easy in the case of metric binary graphs; a fact I haven't seen mentioned yet. $\endgroup$ – Manfred Weis Dec 20 '18 at 19:14
  • $\begingroup$ Not surprising. It is very concrete class of graphs. $\endgroup$ – Fedor Petrov Dec 20 '18 at 19:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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