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

1
vote
0answers
21 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
1
vote
1answer
28 views

Promises in the hidden subgroup formulation of graph isomorphism problem

In the 3rd slide of the talk, Graph isomorphism, the hidden subgroup problem and identifying quantum states, by Pranab Sen, the promise of the problem is defined as follows. Given: $G$: group, ...
3
votes
1answer
25 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 ...
0
votes
0answers
8 views

Nonisomorphic graphs Discrete Math

Find 3 different nonisomorphic graphs with 8 vertices that have the degree sequence 2,2,2,2,2,2,2,2. Answer: An 8-cycle, or two 4-cycles, or a 3-cycle and a 5-cycle. Can someone show me how these ...
1
vote
1answer
75 views

Cayley's theorem : precision

I have the form of Cayley's theorem that doesn't say any more than : for every finite group G there exists n such that Sn has a subgroup which is isomorphic to G. Now I'd be interested in knowing ...
0
votes
2answers
146 views

What's the difference between the automorphism and isomorphism of graph?

What's the difference between the automorphism and isomorphism of graph? In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$, $ f \colon ...
0
votes
1answer
18 views

Graph Isomorphism with Same Degree Sequece

How do I prove that two tree graphs with the same degree sequence are isomorphic (or non isomorphic)? Thanks for the help!
0
votes
1answer
9 views

Show isomorphy by mapping generators onto generators only

If I want to show that two cyclic groups are isomorphic, is it enough to show that their cardinality is the same and that the generators of the groups are mapped onto each other? To be precise: I am ...
0
votes
1answer
42 views

only trivial automorphism on Frucht graph

Why is there only the trivial automorphism on the Frucht graph? We have a rooted tree in the Frucht graph which allows to totally order the vertices. But how does this imply that there is only the ...
0
votes
3answers
44 views

Isomorphisms and Automorphisms

An automorphism is a mapping of a graphs nodes onto it's own nodes. Whereas an isomorphism is the mapping of a graphs nodes onto another graphs nodes. Doesn't this mean the are fundamentally the ...
2
votes
2answers
26 views

Construct Pairs of Non Isomorphic Graphs

I Have the following question : Give three examples of simple, connected graphs, all with 8 vertices with degrees 2, 2, 2, 2, 3, 3, 4 and 4, no pairs of which are isomorphic What is the best ...
0
votes
1answer
101 views

How to determine number of isomorphic classes of simple graph with n vertices, each with degree m?

For HW, I need to find the number of isomorphic classes of a simple graph with 7 vertices, each with degree two. I know I could brute-force it by finding all edge sets that fulfill that criteria, but ...
-1
votes
1answer
68 views

Given three non-isomorphic spanning trees of the complete graph K5, how many trees in each class?

The graph, K5 has 125 different spanning trees, which I beleive fit into three different non-isomorphic classes of spanning trees. However, I'm at odds as to how to figure out how many are in each ...
0
votes
3answers
62 views

Show that the polynomial ring in $n-1$ variables is isomorphic to the polynomial ring in one variable $x_{n}$

For a ring $R$ and for $n \geq 1$, define $ S := R[x_{1},...,x_{n-1}]$ for the polynomial ring in $n-1$ variables with coefficients in $R$. Show that $R[x_{1},...,x_{n}]$ is isomorphic to the ...
0
votes
1answer
36 views

Number of non isomorphic graphs

Let $S$ be a set of all graphs with 30 vertices and 432 edges. Find how many of them are mutually non isomorphic. My approach: we can look at their complements instead. Since $K_{30}$ has ...
1
vote
1answer
60 views

Hypercubes and bipartite graphs not isomorphic to subgraph of k-cube

Is hypercube and k-cube the same? I did see the question in another post here, but I am not able to comment there since I do not have much reputation, and I am not allowed to post a doubt as answer. ...
1
vote
2answers
43 views

Are these two graphs isomorphic?

I have the attached the images of two graphs. I want to know whether two graphs are planar or not. ? I also want to know whether two graphs are planar or not ?
0
votes
3answers
113 views

Find an isomorphism between two graphs

Let $G_1$, $G_2$ be the graphs shown below: Decide if $G_1$ and $G_2$ are isomorphic. If so, exhibit an isomorphism. Otherwise exhibit an invariant property for isomorphism that one of the ...
2
votes
2answers
53 views

Prove or disprove: involves Chromatic numbers, and subgraphs isomorphic to Kr

Prove or Disprove, a) if a graph $G$ contains a subgraph isomorphic to $K_r$, then the chromatic number is greater than or equal to $r$ b) if the chromatic number is great than or equal to $r$, then ...
0
votes
1answer
33 views

Proving the number of subgraphs of $G$ isomorphic to $F$

Let $F$ and $G$ be graphs. Let $sub(F, G)$ denotes the number of subgraphs of $G$ that are isomorphic to $F$, let $inj(F, G)$ denote the number of injective homomorphisms from $F$ to $G$ and let ...
-8
votes
1answer
59 views

Give reason why a graph is not isomorphic [closed]

I need to give an example of two connected graphs with the same degree that arent isomorphic and say why they are not isomorphic
3
votes
2answers
71 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 ...
0
votes
0answers
48 views

Given a graph, is there a way to find the number of isomorphisms?

As the question asks, is there a known way to find the number of isomorphisms of a given graph? I can't find a link anywhere (although I can find the number of distinct isomorphism classes for a graph ...
0
votes
0answers
56 views

Why is a connected planar graph isomorphic to its double dual?

Let $G^*$ be the dual graph of a planar graph $G$ (see wikipedia article). How does one prove that if $G$ is connected then it is isomorphic to $G^{**}$?
0
votes
1answer
84 views

Graph Theory: Isomorphic graphs

Show that the inverse of an isomorphism of graphs is also an isomorphism of graphs. So I just started a graph theory course and am having a little trouble with one of the problems on the homework. I ...
2
votes
1answer
661 views

How to draw all nonisomorphic trees with n vertices?

I have a textbook solution with little to no explanation (this is with n = 5): Could anyone explain how to "think" when solving this kind of a problem? (for example, drawing all non isomorphic ...
-1
votes
1answer
64 views

Graph isomorphism

The definition for graph isomorphism states that two graphs $G_1 = (V_1,E_1)$, $G_2 = (V_2,E_2)$ are isomorphic if there is an isomorphism $f:V_1\to V_2$ such as each $u$ and $v$ vertex from $V_1$ are ...
1
vote
2answers
71 views

Determining if two graphs are isomorphic

I'm supposed to determine if the above graphs are isomorphic. I thought there was because there was a bijection from the set of vertices of graph G to the set of vertices of graph H, and because ...
0
votes
1answer
41 views

Isomorphism of Complete Graphs

I am struggling to understand the concept of isomorphism. By definition, if G and H are two simple graphs so that V(g) and V(h) are the number of nodes in G and H respectively, then isomorphism is ...
0
votes
1answer
46 views

How do I prove isomorphism?

I need to prove this: $$S_{\mathbb{N}}\cong S_{\mathbb{Z}}$$ ($S$ means permutation). I'd like to get ideas how to prove it... Thank you!
0
votes
0answers
35 views

proving that a given graph is isomorphic to an arbitrary graph with same satisfied condtions

Prove that any graph with satisfies the following conditions: each vertex has degree 3 any two adjacent vertices do not have common neighbors ( so no 3-cycles) any two non-adjacent vertices share ...
-6
votes
2answers
51 views

Which of those are isomorphism [closed]

I have here a list. I need to prove which one of them is true (or not) and prove it... $\mathbb{Z}_{21}\times \mathbb{Z}_{50}^*\cong\mathbb{Z}_{420}$ ...
0
votes
2answers
51 views

Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
1
vote
2answers
72 views

Are these graphs Isomorphic

please consider this two graphes. G1: G2: Are they Isomorphic? Is G1 a planer graph? It contains a K 3,3 or k5? thanks alot
0
votes
3answers
116 views

Show two graphs are not isomorphic

I know this graphs are not isomorphic. However they have the same number of vertex and edges, and the same degree sequence, is not the most easy case. If im correct, the graphs are isomorphic if ...
1
vote
1answer
58 views

Proof on ring isomorphism- irreducible

Consider the ring isomorphism $\phi: A \to B$ I have to prove that $a\in A $ is irreducible if and only if $\phi(a)$ is irreducible. By definition, $a$ is irreducible in A if and only if: 1) $a$ ...
2
votes
1answer
70 views

Graph of unbounded degree?

I was reading about The Graph Isomorphism Problem on Wikipedia and the article lists a number of special cases for which the problem can be solved in polynomial time. One of these cases is a graph of ...
0
votes
1answer
49 views

Non-Isomorph trees of a graph

Please consider this graph How many non-Isomorph trees with 4 vertex has this graph? Is there any formula that show number of non-Isomorph trees with $n$ vertices? thanks
1
vote
1answer
75 views

Non-isomorphic simple graphs: order $n$, size $\displaystyle \frac{na}{2}$, degree sequence $(a,a,a,…,a) \in \mathbb{N}^n$

If a simple graph has order $n$, size $\displaystyle \frac{na}{2}$ and degree sequence $(a,a,a,...,a) \in \mathbb{N}^n$ then is it unique up to isomorphism? I thought of this question while ...
2
votes
2answers
31 views

What are multiple isomorphisms?

For example, this graph has "multiple isomorphisms." What does that mean? And could you list them? I don't understand how there can be more than one.
1
vote
2answers
101 views

Prove that the group G defined by a~b=a+b+ab is isomorphic to the multiplicative group of nonzero real numbers.

Question: Prove that the group $G$ consisting of the set $\mathbb{R}\setminus\{-1\}$ with multiplication defined by $a\sim b=a+b+ab$ is isomorphic to the multiplicative group of nonzero real numbers, ...
0
votes
1answer
31 views

Check to see if my isomorphism is correct

Is multiplication modulo $10$ isomorphic to addition modulo $4$? $U(10) = \{1,3,7,9\}$, the identity is $1$, it is a cyclic group of order $4$, with generator $3$. $\Bbb Z_4 = \{0,1,2,3\}$, the ...
0
votes
2answers
1k views

How to find non-isomorphic trees?

"Draw all non-isomorphic trees with 5 vertices." I have searched the web and found many examples of the non-isomorphic trees with 5 vertices, but I can't figure out how they have come to their ...
0
votes
1answer
82 views

Isomorphism between two colored graphs

If there are two graphs whose shape is isomorphic to each other but whose combination of color used in each vertex is not isomorphic to that of other graph, how can I call their relationship? Should I ...
1
vote
1answer
107 views

Complete graph invariant

Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph ...
0
votes
1answer
192 views

Checking for graph isomorphism by hand

I'm working through "A First Look at Graph Theory" by Clark & Holton, and in the first exercise, there are problems asking to check whether different graphs are isomorphic to each other. I find ...
0
votes
1answer
77 views

Determine all possible automorphisms of a graph

Let $G$ be the undirected graph whose vertex set is $\{a,b,c,d,e\}$ and edge set $\{ab, ae, bc, be, cd, ce, de\}$. The graph is drawn below: Let $V$ denote the set of vertices of the graph G ...
3
votes
2answers
5k views

Prove two graphs are isomorphic

I have identified two ways of showing it isomorphic but since it is a 9 mark question I dont think i have enough and neither has our teacher explained or given us enough notes on how it can be ...
1
vote
1answer
57 views

Systematizing graph morphisms

Trying to systematize possible notions of graph morphisms I came about the following classification: A morphism $f$ which sends a graph $G$ to another graph $G'$ is – first of all – ...
2
votes
1answer
140 views

Proving that a graph is self complementary

I've been given the following adjacency matrix: $$\left(\begin{array}{cccccccc} 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 ...