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

399 questions
Filter by
Sorted by
Tagged with
0answers
26 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$ ...
1answer
86 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 ...
0answers
15 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 ...
1answer
23 views

### Tree isomorphism

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 ...
0answers
25 views

### Is observation enough verification for equivalency of adjacency matrices (required to prove that two graphs are isomorphic)?

Determine whether the following graphs are isomorphic. Labelling the graphs in the above manner contructs a bijection between the sets of vertices. However, to verify that it indeed sends edges to ...
1answer
44 views

0answers
50 views

### Finding coloring with no subgraph isomorphism

This is a twist on standard subgraph isomorphism. Say I have two graphs $G(V,E)$ and $H(V',E')$ and the vertices in each graph are colored with one of $t$ colors. The subgraph isomorphism exists if ...
1answer
36 views

### Detecting graph topology.

I have a set of graphs and I need to classify them with respect to their topology. Is there an algorithm which can detect the topology (random, regular, scale-free, etc.) of a given undirected graph?
1answer
45 views

### proof regarding isomorphic graphs

I am working on a graph theory proof but facing problems regarding how to approach to prove it Consider the following statement: Given a set of n graphs, {G1, G2, · · · , Gn}, some of the pair of ...
1answer
30 views

### Prove two graphs are isomorphic from geometric duals. [closed]

Prove that two graphs $G_1$ and $G_2$ are isomorphic if and only if their geometric duals $G_1^*$ and $G_2^*$ are also isomorphic.
2answers
30 views

### How to determine isomorphism in simple, connected (regular) graphs?

I am learning about regular graphs and have found that there are only 5 different options for a simple connected 3-regular graph with 8 vertices (source: http://www.mathe2.uni-bayreuth.de/markus/...
1answer
21 views

### Additional criteria to establish graph isomorphism apart from moving vertice and renaming?

The task is to check whether the two graphs are isomorphic: The solutions is given as: The instructions say we can rearrange the vertices and rename them. However looking at the solution I could ...
2answers
47 views

### How many non-isomorphic full binary trees are there?

A full binary tree is a rooted tree where every node has either zero children or two children. My question is, how many non-isomorphic full binary trees are there, countably many or uncountably many? ...
1answer
63 views

### How to find Graph that is not isomorphic?

I need to find Graph G with degree sequence (5,5,4,4,4,4,4,2,2,2,2,2) constructed with Havel Hakimi method, that will not be isomorphic with G. Is it even possible?
0answers
40 views

### Graph Isomorphism for given graphs

Prove that the graph $G_1$ and $G_2$ are isomorphic. I know the definition of graph isomorphism, and can informally prove why this is true. However, it would be welcomed to see the formal proof, ...
0answers
34 views

### Isomorphism between graphs

Are the graphs G1 and G2 isomorphic? I think that the graphs are not isomorphic because G2 has a cycle tuwzt, where all vertices have deegree 4. No such cycle can be found in G1. Therefore because ...
0answers
14 views

### Most efficient Algorithm to Decide if a Color-Preserving Isomorphism exists between Digraphs?

I am working on the graph isomorphism problem for colored digraphs, that is deciding whether a color-preserving isomorphism exists between two such graphs. Note: In my case, digraphs can be cyclic and ...
1answer
102 views

### Matrix representation of graph to determine if two graphs are isomorphic

Based on the definition of Isomorphism i.e two graphs are isomorphic if there exists a Bijection between Vertices sets and Edge sets of the two graphs. Since a graph can be represented as a Matrix ...
1answer
32 views

### Proof Paths are Preserved

I am trying to prove that for graphs $G$ and $H$ with an isomorphism existing from $G$ to $H$, $p$ is a path in $G$ from $u$ to $v$ if, and only if, $f(p)$ is a path in $H$ from $f(u)$ to $f(v)$. My ...