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
4k 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
236 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.
5
votes
3answers
7k 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
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 ...
3
votes
2answers
185 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
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 ...
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?
2
votes
2answers
91 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 ...
2
votes
1answer
94 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
37 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
177 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
340 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
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 ...
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 ...
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 ...
2
votes
1answer
218 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 ...
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
2answers
265 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
77 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
31 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
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!
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
2answers
30 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
1
vote
1answer
131 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 ...
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 ...
1
vote
3answers
291 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 ...
1
vote
2answers
152 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
90 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
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
17 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
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
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, ...
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 ...
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
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
1answer
88 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
119 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
460 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
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 ...
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?
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 ...
1
vote
1answer
15 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
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 ...
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^{**}$?
1
vote
1answer
64 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
91 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
96 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. *----------* /|\ | | | | ...