# Questions tagged [graph-isomorphism]

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

428 questions
Filter by
Sorted by
Tagged with
39 views

### Finding an isomorphism between an infinite tree and a subgraph of $\mathbb{Z}^3$

I was wondering if there exists a construction of an infinite tree, with some properties, that is isomorphic to subgraph of $\mathbb{Z}^3$. Notation Let $\Gamma_n$ denote the tree's vertices at ...
34 views

62 views

### How to prove that the 2 graph matrices describe the same graph?

To simplify the question, we suppose that: All verticles of $G$ are $v_1, v_2,...,v_n$ There is no edge which connect it with itself. $G$ is non-directed. There are at most one edge between 2 ...
46 views

### Shouldn't any relabelling of vertices in a graph preserve isomorphism?

Say $G$ and $H$ are two isomorphic graphs. There is the following theorem: Two simple graphs $G$ and $H$ are isomorphic if and only if there exists a permutation matrix $P$ such that $A_G=PA_HP^t$. ...
39 views

### Isomorphy between graphs

I am asked to find a undirected graph that is Isomorphic to a directed graph. Does that even make sense? directed graph with 3 nodes My first thought was a cycle with 3 Vertices, but I don't feel ...
67 views

### How many graphs on [$n$] vertices are isomorphic to $K_n$

Total Number of Graphs on a vertex set $[n]$ = $2^{\binom{n}{2}}$ Since the total number of isomorphisms is equivalent to total number of bijection $\implies$ $n!$ What it would tell if divide these ...
53 views

### What kind of graph coloring is this?

Assume a very simple graph with 3 points: V0—V1—V2 The following represent all the different possible colorings using 3 colors. I’ve labelled all of the types of colorings that are isomorphic (is that ...
22 views

### Relationship between the sizes of orbits of nodes

About a year and a half ago I wrote a certain proposition offhand in a proof. I must have thought it was trivial at the time and so did not prove it, but months later it is not quite so trivial to me ...
1 vote
68 views

36 views

39 views

### Cycle Decomposition as Colored-Edges? How?

In a proposition of graph isomorphism I find that for a generator $σ \in S$ (the set of generator of a group), edges can be added to a directed edge-colored graph $X(G)$ of color $σ$ corresponding to ...
1 vote
116 views

### How can I label vertices of the graph, so they are the same as on the other labeled graph?

Is there some algorithm to label equivalent vertices of unlabeled graph? For example, suppose I have two distinct graphs $G_1$ and $G_2$, and they are isomorophic. However, $G_1$ has labeled vertices ...
28 views

### How to create a special graph?

I wish to generate an undirected lattice graph $G$ with following features: It has $m\times n$ vertexes; Each vertex has only two kinds of labels ($0$ or $1$); Every $t\times t$ subgraph is unique. ...
36 views

### For two graphs to be isomorphic should the set of vertices be the same?

We have three persons $P_1, P_2$ and $P_3$. $P_1$ is the father of $P_2$ and $P_3$ is the wife of $P_2$. I am making two graphs with edges edges representing the relation. Say I have one graph $G_1$ ...
1 vote
156 views

### Isomorphism classes of trees with maximum degree $3$ and $6$ vertices

List the isomorphism classes of trees with maximum degree $3$ and $6$ vertices. I start with the star $K_{1,3}$ and append vertices accordingly to achieve $6$ vertices keeping maximum degree $3$. I ...
17 views

### what does $1/n$ times the expected number of edges per vertex in a finite poset on $n$ points approach as $n$ goes to infinity?

Let $S_n$ be a maximal set of inequivalent posets on $n$ points (i.e., one with maximum possible cardinality). Let $E_n$ be the total number of edges in $S_n.$ Clearly $|S_n|$ and $|E_n|$ depend only ...
I'm trying make a proof for this statement : $T=(V;E)$ is a tree, if $f,g$ are two isomorphism of T such that for each leaves $u \in T$ we have $f(u)=g(u)$ then $f=g$ I can imagine how this is true ...