Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ where $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right) $, where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$. Here, $R_{k,e}$ represents edges between $H_k, H_e$. The matrix $H$ looks like- $$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\ R_{(x,x-1)^{T}} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ R_{(x,1)^{T}} & R_{(x-1,1)^{T}} & R_{(x-2,1)^{T}} & \dots & \dots &H_{1} \end{bmatrix}$$.

Each $M_{k,e}$ can have exactly $6$ vertices, $3$ vertices in $H_k$ and $3$ vertices in $H_e$.

Fact: $R_{k,e}$ is a non-symmetric matrix of dimension $3 \times 3$ . It is clear that each distinct $R_{k,e}$ can appear maximum $b$ times where $b \leq n^{9}$, since there are maximum $n^{3}$ different possible $H_k$ and $n^{3}$ different possible $H_e$ .

Problem: Is there any result against the following statement-

Each distinct $R_{k,e}$ can appear maximum $\sqrt b \leq n^{3}$ times for different pair of $H_k, H_e$.

I am assuming the statement is correct.

Context: This is related to "individualization" of $k$ vertices of a graph. The problem is related to my earlier query Graph Coloring: Two adjacent vertices share same color.

  • 1
    $\begingroup$ This question has received only very little attention so far -- maybe you wish to edit. $\endgroup$ – Stefan Kohl May 8 '17 at 15:45
  • $\begingroup$ @StefanKohl , thnks for ur attention and advice but am not going to do anything with this post, actually am thinking how to delete my account of MOSE... tnx though. $\endgroup$ – Jim May 8 '17 at 15:50

Your Answer

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

Browse other questions tagged or ask your own question.