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

18
votes
4answers
3k 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, ...
7
votes
2answers
188 views

Build graph with exactly n automorphisms

Construct graph with exactly distinct n automorphisms. For n $\geq$ 2. I wonder if we can just take an asymmetric graph, such as this one as building block.
4
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 ...
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 ...
3
votes
2answers
160 views

Number of non-isomorphic ways the following graph can be labelled

In how many non-isomorphic ways can the following graph be labelled? Ignore the numbers on the graph vertices. I got two different answers and I'm not sure which one of my reasoning is right: 1) ...
3
votes
1answer
28 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 ...
2
votes
1answer
73 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 ...
2
votes
2answers
33 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.
2
votes
1answer
145 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 ...
2
votes
1answer
301 views

Finite Vertex-Transitive Planar game of Civilization?

If you have played games in the Civilization series, you will have noticed that the Earth is represented in a simplified and profoundly unsatisfying way. It is wrapped around the curve of a cylinder ...
2
votes
2answers
28 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 ...
2
votes
2answers
55 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 ...
2
votes
1answer
775 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 ...
2
votes
1answer
211 views

Generating non-isomorphic graph by adding two edges to a fixed graph

I am given a graph $G$ a fixed vertex $v \in V(G)$ and sets $S_1,S_2 \subseteq V(G).$ The problem I am currently studying requires to answer the following question Compute all non-isomorphic ...
1
vote
2answers
227 views

Can someone intuitively explain how we can tell if two graphs are isomorphic?

I'm having a hard time understanding the explicit definition and was hoping someone could help me make a connection between the theory of isomorphism and the way it's actually applied (ex. how can we ...
1
vote
2answers
73 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
1
vote
2answers
75 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 ...
1
vote
2answers
44 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 ?
1
vote
2answers
110 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, ...
1
vote
1answer
85 views

Can someone help me solve this misunderstanding please.

Is it a good way to determine isomorphic of two graphs by comparing their adjacent vertices? If their is a different then they are not isomorphic? If they have the same then they are isomorphic? Since ...
1
vote
1answer
30 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, ...
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 ...
1
vote
1answer
112 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
vote
1answer
68 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
1answer
78 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 ...
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 ...
1
vote
1answer
392 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
1answer
17 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
1
vote
0answers
25 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
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$ ...
1
vote
1answer
63 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 – ...
1
vote
0answers
37 views

Rating and Scoring Graphs based on physical properties

i am busy working on a project related to L-systems. The basic idea is to generate graphs from these L-strings and rate them based on some physical traits, such as self similarity.... Is there any ...
1
vote
1answer
94 views

Graph isomorphic to symmetric group

Show why the symmetry group of the graph below is isomorphic to $S_3 \times S_2$. $S_3$ and $S_2$ are symmetric groups and $\times$ denotes direct product. *----------* /|\ | | | | ...
0
votes
2answers
158 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
3answers
121 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 ...
0
votes
1answer
79 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 ...
0
votes
1answer
197 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
2answers
153 views

Finding an isomorphism between $(U\otimes V)^{\mathsf T}$ and $B(U \times V,\mathbb{R})$

Prove the isomorphism between $(U\otimes V)^{\mathsf T}$ and $B(U \times V,\mathbb{R})$, where $B$ is the collection of all bi-linear mappings. In order to do so, give a natural isomorphism between ...
0
votes
1answer
29 views

Finding all mapping between two isomorphic graphs

Is there any formula for counting all the mappings between two isomorphic graphs? I have the following two graphs. and I am trying to find the mappings in the following way. For each edge in ...
0
votes
1answer
43 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
145 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 ...
0
votes
1answer
35 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 ...
0
votes
1answer
47 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
1answer
50 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
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
88 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 ...
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
3answers
63 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
86 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 ...
0
votes
1answer
44 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 ...