1

The question is, "is it true or false? state your reasons. There are some isomorphic graphs even though their incidence matrices are different." Is it true? OR false? If it is true, could you show me some examples?

Thank you.

Nitin Uniyal
  • 7,946
Jay Shin
  • 11
  • $\left(\begin{smallmatrix}0&1&0\1&0&0\0&0&0\end{smallmatrix}\right)$ and $\left(\begin{smallmatrix}0&0&1\0&0&0\1&0&0\end{smallmatrix}\right)$. – vadim123 Jun 17 '16 at 05:07
  • @vadim123 The OP asks about "incidence graphs" whatever that might mean. My guess is he means "incidence matrices". The matrices in your example seem to be adjacency matrices. – bof Jun 17 '16 at 05:20
  • 1
    I don't know what an "incidence graph" is. Do you mean "incidence matrix"? What convention do you use for incidence matrices? If a graph has $m$ vertices and $n$ edges, does its incidence matrix have $m$ rows and $n$ columns, or is it $m$ columns and $n$ rows? – bof Jun 17 '16 at 05:23
  • @bof: Note that the title on the Question says "incidence matrices", so the text in the body could well be simply a typo. – hardmath Jun 17 '16 at 05:46
  • The question has no typo. It's not an adjacency matrix but an incidence matrix, which has a row as edges and columns as vertices. Of course, even though if adjacent matrices between two graphs are different, both graphs could be isomorphic. But, incidence matrices? – Jay Shin Jun 18 '16 at 07:26

1 Answers1

1

Take $A(G_1)=$ $$\begin{pmatrix}v_1:1&0&0\\v_2 :1&1&0\\v_3 :0&1&1\\v_4 :0&0&1\\ \end{pmatrix}$$ and $A(G_2)=$ $$\begin{pmatrix}v_1 :0&0&1\\v_2 :0&1&1\\v_3 :1&1&0\\v_4 :1&0&0\\ \end{pmatrix}$$ where $v_i$, $1\le i\le 4$, are the vertices and the each column vector correspond to an edge $e_j$ , $1\le j\le 3$. Obviously $A(G1)\ne$$A(G_2)$ but their corresponding graphs $G_1$ and $G_2$ are isomorphic.

Note: Consider $e_1$,$e_2$ and $e_3$ above the top row of the matrix so that $A(G_i)$ represents an incidence matrix. I tried my best to do the same but still struggling with Mathjax on mobile.

Nitin Uniyal
  • 7,946