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
2answers
33 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
0
votes
0answers
48 views

Show that the number of isomorphism classes of tree on n vertices is exponentially large as a function on n.

I am currently trying to answer this question: 'Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n−2}}{n!}$ and hence that this is exponentially large as a ...
1
vote
1answer
132 views

Number of isomorphism classes of a tree on n vertices

I'm currently trying to solve this problem: "Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n-2}}{n!}$." I'm pretty stumped to be honest. I know of Cayley's ...
0
votes
1answer
24 views

Is the number of simple circuits of a particular length preserved in two isomorphic graphs?

If two graphs are isomorphic, and one has a simple circuit of a particular length, must the other graph also have a circuit of the same length? Do they also have to have the same number of such ...
2
votes
2answers
378 views

Is there any way, except trial and error, to find an isomorphism for these two graphs?

How can I tell that these graphs are isomorphic and how can I show it?
0
votes
2answers
36 views

Concept: The graph component

I have the following definition for a Component of a graph: A subgraph $H$ of a graph $G$ is a component of $G$ if $H$ is a maximal connected subgraph of $G$, ...
0
votes
1answer
56 views

Any two abelian group of order 8 must be isomorphic

TRUE/FALSE :Any two abelian group of order 8 must be isomorphic SOLUTION: True The problem of finding all abelian groups of order 8 is impossible to solve, because there are infinitely many ...
1
vote
1answer
18 views

Vertex degree and graph isomorphism

Suppose I have two simple graphs $G(V,E)$ and $H(V,E)$ with number of vertices $N$. And $\forall i \quad \text{such that}\quad 0<i<N$ No:of elements in $V(G)$ with degree $i $ = No:of elements ...
0
votes
1answer
35 views

Proving two graphs are isomorphic in polynomial time - Bondy/Murty - Graph Theory Page 6

I am trying to do the below problem: Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since it is $3\text{-regular}$. I ...
0
votes
1answer
32 views

Proof verification: (Pretty pictures :) )Showing two graphs are not isomorphic. Bondy/Murty - Graph theory Page 5

I want to show the below two graphs are not isomorphic. Treat the left as graph $\bf G$ and the right as graph $\bf H$. $\bf G$ and $\bf H$ are not isomorhpic: Although we have a bijective mapping ...
1
vote
2answers
59 views

How to calculate the number of automorphisms of a given graph?

How do determine the number of isomorphisms that a graph has to itself? For instance, suppose we have the following graph: How do I determine how many isomorphisms there are from G itself?
0
votes
1answer
20 views

How can I show complete graphs are determined by spectrum?

I understand how to prove a complete graph $K_n$ has spectrum $\lbrace -1^{(n-1)},n-1 \rbrace$. However I am having difficulty proving that the spectrum uniquely determines the complete graph. ...
1
vote
1answer
45 views

$3$-connected graph isomorphism problem

If $G$ is $3$-connected, then $G$ contains a subgraph isomorphic to $H$, where $H$ is obtained from $K_4$ by replacing the edges of $K_4$ by internally disjoint paths. Any hints and proofs are ...
1
vote
1answer
18 views

isomorphism of graph

I have a doubt about an example of isomorphism of graphs. I am looking at the notes of group theory by Donald Kreher. (http://www.math.mtu.edu/~kreher/ABOUTME/syllabus/GTN.pdf). Please see page 9 ...
1
vote
2answers
33 views

Are these graphs isomorphic?

Are these 2 graphs isomorphic? (sorry for the bad picture quality) For the solution: 1) They both have 8 vertices 2) They both have 12 edges 3) They both have 8 vertices of degree 3 4) Is this ...
1
vote
2answers
32 views

Isomorphism vs equality of graphs

I have just started studying graph theory and having trouble with understanding the difference b/w isomorphism and equality of two graphs.According what I have studied so far, I am able to conclude ...
1
vote
0answers
26 views

How many different graphs are there with a given degree-sequence?

Let G be a simple undirected graph. If it has at most $4$ edges, there is only one graph for any degree-sequence, but for $n = 5$, the situation changes. There are $34$ different (non-isomorphic) ...
1
vote
1answer
25 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 ...
0
votes
1answer
45 views

Calculating the number of isomorphic classes of complete bipartite graph

How many isomorphism classes of complete bipartite graphs have exactly 10 vertices? I don't understand what the question is asking or how to go about solving it.
0
votes
1answer
38 views

Graph isomorphism problem for labeled graphs

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
1
vote
1answer
48 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 ...
2
votes
0answers
30 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
33 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
31 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 ...
1
vote
1answer
16 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
87 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
203 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 ...
1
vote
1answer
23 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
19 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
46 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 ...
1
vote
3answers
52 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
32 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 ...
1
vote
1answer
221 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
179 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
69 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 ...
1
vote
1answer
52 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
106 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
45 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
3answers
293 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
69 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
42 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 ...
3
votes
2answers
74 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
55 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 ...
1
vote
0answers
81 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
95 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
2k 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 ...
0
votes
1answer
72 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 ...
2
votes
2answers
92 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
69 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
48 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!