Skip to main content
edits in reply to Fedor's comment
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Estimating Maximal-Clique Sizeof Metric Graphs via Matrixthe Rank of their Adjacency Matrix

letLet $\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?

Estimating Maximal-Clique Size via Matrix Rank

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$.

Question: is it 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?

Estimating Maximal-Clique of Metric Graphs via the Rank of their Adjacency Matrix

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?

Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Estimating Maximal-Clique Size via Matrix Rank

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$.

Question: is it 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?