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

Filter by
Sorted by
Tagged with
0
votes
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$ ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
-1
votes
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 ...
0
votes
1answer
44 views

Is equivalent labelling enough to prove isomorphism between two graphs?

Determine whether the following graphs are isomorphic. Labelling vertices of both graphs as $u_1,u_2,u_3,u_4,v_1,v_2,v_3,v_4$ in the order given above, we see that these graphs are bipartite with $...
0
votes
0answers
17 views

Determine isomorphism classes for pairs of families from paths, cycles and bipartite graphs

Consider the family of graphs $A=\{\text{paths}\}$, $B=\{\text{cycles}\}$ and $D=\{\text{bipartite graphs}\}$. For each pair of these families, determine all isomorphism classes of graphs that belong ...
0
votes
0answers
28 views

“Let $G \cong H$. $G$ is planar graph $\Leftrightarrow$ $H$ is planar graph.”

"Let $G \cong H$. In this case $G$ is planar graph $\Leftrightarrow$ $H$ is planar graph." If this proposition true, prove that. If false, give an example. This question in my exercise book. ...
-1
votes
1answer
11 views

How many non-isomorphic graphs can be constructed from $n$ vertices where each vertex has the same degree?

I honestly do not know how to begin to solve this. I am assuming that the answer is zero since they have the same degree sequence. That is, it's possible for a graph deduced from these $n$ vertices to ...
0
votes
1answer
37 views

Determine if the two graphs are isomorphic

Let G be the graph with vertex and edge sets $$V = \{1, 2, 3, 4\}$$ and $$E = \{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$$ and H be the graph with vertex and edge sets $$V = \{a, b, c, d\} $$and $$E =...
1
vote
1answer
43 views

Is there a way to know how many non-isomorphic spanning trees there are for a graph?

I have a big doubt: Is there a way to know how many non-isomorphic spanning trees there are for a graph? In a Spanning Tree there are no cycles, one less thing to worry about.
0
votes
1answer
33 views

Unsure of graph isomorphism

Are the following sets of graphs isomorphic? I believe the first set (the rooted trees) are, and with the second set (the free trees), I notice that both trees have 2 vertices with degree 3, one with ...
1
vote
1answer
34 views

Graphs with same degree sequence and same number of vertices isomorphic? [duplicate]

if there are two graph $G$ and $H$ that have same number of vertices, and their degree sequences are the same. Does this mean that they are isomorphic ?
0
votes
0answers
43 views

Dual of dual of planar graph $G$ is isomorphic to $G$ if and only if $G$ is connected.

I have been asked to show that the dual of the dual, $(G^*)^*$, of a planar graph $G$ is isomorphic to $G$ if and only if $G$ is connected. I understand the reasoning in the answer one but that cannot ...
0
votes
0answers
23 views

What kind of order morphism is $h$?

Let $X=\Bbb N^+/\langle2\rangle$ where $\langle2\rangle$ represents multiplication by $\{2^i:i\in\Bbb Z\}$ so for example $x=3\cdot\langle2\rangle$ is an element of $X$. For each $x\in X$ let $\succ$ ...
0
votes
0answers
29 views

Maximal number of edges

Given a simple graph on 15 vertices consists of several (more than one) isomorphic connected components. What is the maximal possible number of edges in this graph? I tried by using the bipartite ...
1
vote
1answer
35 views

Unique four-regular, simple planar graph such that every face is bounded by three edges

A question on my graph theory exam asked us to find how many $4$-regular, simple planar graphs there are up to isomorphism such that every face, including the outer face, is bounded by three edges. I ...
-2
votes
1answer
45 views

Isomorphic 2-graphs [closed]

Two graphs Can we say that these two graphs are isomorphic? I think no because $\deg^-(c) \ne \deg^-(g)$. The solution says they are isomorphic, but I don't understand why. Am I wrong?
0
votes
0answers
17 views

How to count the number of subtrees in a m-ary tree that is subgraph isomorphic to a another m-ary tree?

Let there be two directed $M$-ary ($k$-ary) trees, $T_a$ and query tree $T_b$. I'm interested to find how many subtrees $|S_a|$ there are in $T_a$ that is subgraph isomorphic to $T_b$. $T_a=$ data ...
0
votes
1answer
41 views

How many distinct isomorphism types are there of an unlabeled two vertex graph? With labels?

How many isomorphisms are there of unlabeled 2 vertex graphs, and how many of labeled 2 vertex graphs? Loops are allowed. I know this is trivial but I suspect there're 4 unlabeled, no loops, one edge; ...
0
votes
1answer
40 views

How to prove a bijection exists between two sets of tuples?

let $C_{1} = \{a_{11}...a_{i1}\}$ and $C_{2} = \{a_{12}...a_{j2}\}$ also, let $C'_{1} = \{a'_{11}...a'_{i1}\}$ and $C'_{2} = \{a'_{12}...a'_{j2}\}$. Where $|C_1| = |C'_1| = i$ and $|C_2| = |C'_2| = j$...
0
votes
2answers
36 views

The number of all pairwise non-isomorphic graphs

How to prove that if $n = 4k + 2$ or $n = 4k + 3$, then the number of all pairwise non-isomorphic graphs with n vertices is even. Any ideas on how to do this?
1
vote
1answer
24 views

Find all pairwise non-isomorphic graphs

Task: Find all pairwise non-isomorphic graphs with $n\leq 4$ vertices. I think that for $n = 1$ there is 1 such graph, for $n = 2$ - two, for $n = 3$ - there are 4 of them (shown in the photo), for $n ...
1
vote
1answer
21 views

Are these 2 graphs isomorphic? Question regarding the placement of subgraphs

So im having trouble figuring out the answer in this problem. Everything seems ok (same number of vertices, degrees etc) but i would guess that they are NOT isomorphic because in the second graph ...
1
vote
0answers
27 views

Roots producing isomorphic trees

Is there existing terminology for the following property of a rooted tree? I'd like to know how many choices of root node can produce an isomorphic tree. This is different from the number of ...
2
votes
1answer
35 views

Checking if two digraphs are isomorphic from their adjacency matrices

Wikipedia says that, given digraphs $ G_1 $ and $ G_2 $ whose adjacency matrices are $ A_1 $ and $ A_2 $ respectively, $ G_1 $ and $ G_2 $ are isomorphic if and only if there exists a permutation ...
0
votes
1answer
12 views

Isomorphic graphs definition, understanding of the application of permutation matrix

I was thinking about the definition for two graphs being isomorphic: Basically considering two graphs $\mathcal{G}, \, \mathcal{S}$ they are known to be isomorphic if they are essentially identical in ...
-1
votes
1answer
54 views

What's the consequence of telling isomorphic graphs apart for the complexity class of a graph property? [closed]

A graph property is a class of graphs with the property that any two isomorphic graphs either both belong to the class, or both do not belong to it. A graph invariant is any ...
5
votes
1answer
105 views

How to judge the isomorphism of two drawings of same graph?

We say two drawings of a graph are isomorphic if there is a homeomorphism of the surface that maps one drawing to the other. But in actual operation, I find it quite difficult to determine whether two ...
1
vote
1answer
39 views

Number of non-isomorphic graphs

A graph on 8 vertices, each has degree 5. I need to find the number of such graphs, which are non-isomorphic. So, it's easy to show, that there are $|E| = \frac{8 \cdot 5}{2} = 20$ edges in such ...
0
votes
0answers
38 views

Graph Theory Question regarding Isomorphism and Matrix Transposes

How would one prove true or false the statement "for an I, incidence matrix of a graph G, and a J, incidence matrix of a graph H, it is impossible for G and H to be isomorphic AND for the product ...
0
votes
1answer
29 views

Equivalence relation on graphs identifying degrees

I consider a connected simple finite graph $G$ and I define the equivalence relation $v\sim w$ on its vertex set such that $v\sim w$ if and only if $\mathrm{deg}(v)=\mathrm{deg}(w)$. I found that it ...
3
votes
1answer
49 views

Are these 2 graphs isomorphic (with illustrations and counter examples that appear not to preserve adjacencies)?

The following labeled slide was presented in a first year discrete mathematics course. However, the adjacencies don't appear to be preserved (see the second illustration below). If the vertices in ...
3
votes
2answers
79 views

Are two graphs isomorphic?

Are the two graphs isomorphic? $$G_1=\begin{bmatrix} a & b & c & d & e & f \\ b & a & a & c & d & a \\ c & c & b & e & f & d \\ f & &...
2
votes
2answers
35 views

Graph automorphisms and the diamond graph

I thought I understood graph automorphisms, but looking at a specific example is tripping me up. Consider the diamond graph: Apparently, the Klein 4-group is the automorphism group of this graph. The ...
2
votes
1answer
59 views

Identifying isomorphic graphs

I'm having trouble solving this exercise I found about isomorphic graphs. It reads Among the following graphs, which pairs are isomorphic? For each pair that are isomorphic, describe an isomorphism (...
2
votes
0answers
68 views

Algebraic Graph Theory

$V$ is set of size $n$ and $\operatorname{Sym}\left(V\right)$ denote the group of permutation of $V$. $E\left(K_V\right)$ denote the set of edges of complete graph with $n$ vertices. For $g\in\...
1
vote
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 ...
1
vote
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?
2
votes
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 ...
-1
votes
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.
1
vote
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/...
0
votes
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 ...
0
votes
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? ...
0
votes
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?
0
votes
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, ...
3
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...

1
2 3 4 5
8