Two graphs $G$ and $H$ are isomorphic if they have a function $f$ which provides an exact pairing of vertices in the two graphs such that for any adjacent vertices $u,v\in \{\mbox{set of vertices of }G\}$, $f(u)$ and $f(v)$ are also adjacent in $H$.

learn more… | top users | synonyms

21
votes
4answers
5k views

Are these 2 graphs isomorphic?

They meet the requirements of both having an $=$ number of vertices ($7$). They both have the same number of edges ($9$). They both have $3$ vertices of degree $2$ and $4$ of degree $3$. However, ...
8
votes
2answers
301 views

Reorder adjacency matrices of regular graphs so they are the same

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ ...
3
votes
1answer
38 views

Confusion about the hidden subgroup formulation of graph isomorphism

I am going through Quantum factoring, discrete logarithms and the hidden subgroup problem by Richard Jozsa. On page 13, the author discussed the hidden subgroup problem (HSP) formulation of the graph ...
3
votes
2answers
87 views

Is $\exp:\mathbb{M_n}\to\mathbb{M_n}$ injective?

This is related to a personal exploration of isometries of directed graphs, motivated by my son's Lego Duplo train tracks and identifying "interesting" layouts. If $M$ is the adjacency matrix for a ...
1
vote
1answer
249 views

Number of isomorphism classes of a tree on n vertices

I'm currently trying to solve this problem: "Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n-2}}{n!}$." I'm pretty stumped to be honest. I know of Cayley's ...