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

22
votes
4answers
5k 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, ...
12
votes
5answers
840 views

How to show these two graphs are not isomorphic?

In my class they gave me some necessary conditions for two graphs to be isomorphic, these two graphs satisfy all of them but I don't think they're isomorphic: Degree sequences are equal. Same amount ...
8
votes
2answers
326 views

Reorder adjacency matrices of regular graphs so they are the same

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ ...
7
votes
2answers
347 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
4answers
12k 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 ...
4
votes
0answers
50 views

How to determine if these graphs are isomorphic?

I had this question on my last Discrete exam: (the missing vertex on graph G is vertex d) I did prove that the graphs were isomorphic, but my teacher said that I matched up my vertices wrong. ...
3
votes
2answers
87 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
226 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
3k 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 ...
3
votes
1answer
66 views

All non-isomorphic graphs

How can I find all non-isomorphic graphs with 2, 3 or 4 nodes, including not-connected ones? I know that to graphs $G_1$ and $G_2$ are isomorphic, if there is a bijective depiction $f: V(G_1) ...
3
votes
1answer
66 views

Isomorphisms of infinite graphs that are fixed on a set of vertices

Suppose we have two infinite directed graphs $\langle V,E\rangle$ and $\langle V,E^*\rangle$, and a set $A \subseteq V$ such that, for all finite $X \subseteq A$, there is an isomorphism from $\langle ...
3
votes
1answer
39 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
416 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
3answers
76 views

Nice Isomorphic Question and way of finding Quickly?

I see a question about Isomorphic Graph. the question is: The first line graph is not isomorphic with which one in the second line? How we can find isomorphic graph without knowing some geometry map ...
2
votes
2answers
151 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
131 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
1answer
147 views

Solution of Graph Isomorphism in current literature.

As of 2008, the best algorithm for graph isomorphism (Babai & Luks 1983) has run time $2^{O(\sqrt(n log n))}$ for graphs with n vertices. Does this algorithm gives a yes / no answer or provide ...
2
votes
1answer
51 views

What is a graph isomorphism?

I am trying to under isomorphism in graphs, and from what I know, if graph A is isomorphic to graph B, then you could basically just rearrange the nodes in A, while keeping the edges connected the ...
2
votes
2answers
48 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
18 views

Subgraph isomorphism problem

Subgraph isomorphism problem is an NP-hard problem. However, if the subgraph size is constant (assume $k$), then it can be polynomial time solvable. The most easiest way is that: Randomly obtain $k$ ...
2
votes
1answer
292 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
520 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
1answer
275 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
1answer
55 views

Creating a Bijection to check if Graphs are Isomorphic

To prove that two graphs are isomorphic I was taught to first consider the bijection between the two graphs. I was never taught however the rules when coming up with the bijection. Is my only rule, ...
2
votes
1answer
39 views

Adding an edge and a vertex to non-isomorphic graphs

Let $G$ and $H$ be two non-isomorphic simple graphs of equal order and equal size. Suppose I am to add a vertex $v$ and and edge $e$ incident to $v$ to $G$ and $H$. By add I mean to connect $v$ to ...
2
votes
2answers
52 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
114 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
100 views

Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?

Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph. Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite. I know that $G$'s number of faces is ...
2
votes
0answers
14 views

are all transitive reductions of a graph isomorphic?

Transitive reduction of a graph is not unique. Take this example: Now if we remove the labels, the two reduced graphs are isomorphic: are all transitive reductions of a directed graph isomorphic ...
2
votes
0answers
47 views

Why is the graph of 4 nodes and 2 edges not self-complementary?

I am having some trouble seeing why a graph of 4 nodes and 2 edges is not self-complementary such that G is isomorphic to G bar (G complement) (please see the attachment below). I know that the number ...
2
votes
0answers
42 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
327 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
90 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
60 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
55 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
28 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
1answer
142 views

Can a method related to “Weisfeiler-Lehman Method” provide better time complexity for Graph Isomorphism than existing result?

Cai-Furer-Immerman showed that the W-L(Weisfeiler-Lehman ) hierarchy cannot distinguish general graphs except at linear dimension. Even besides CFI's result, there is good reason to believe that ...
1
vote
2answers
44 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
1
vote
1answer
253 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
98 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
1answer
52 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
3answers
829 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
205 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
101 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
67 views

Finding Automorphisms of Irregular graph through Regular Sub-Graphs.

Objective : To find a set of permutations for a irregular graph which is also a set of automorphism. This finding process uses permutations of 2 regular subgraphs of the given graph. Description and ...
1
vote
1answer
61 views

Number of Automorphisms of a Irregular Graph.

I have been looking for results on number of graph automorphisms of irregular graph(upper and lower bound). I searched , but could not find anything which can be used directly. Say, $G$ is $k$ ...
1
vote
1answer
26 views

A succinct proof that the given graphs (red $K_n$ drawn cyclically, plus blue $2$-paths between closest vertices) have dihedral automorphism groups?

Take the complete graph $K_n$ ($n \geq 3$), on the red-colored vertex set $\mathbb{Z}_n$, say, and add a blue-colored $2$-path between each pair of vertices $v$, and $v+1$, we get a sequence of graphs ...
1
vote
1answer
55 views

Graph Isomorphism of Complete Graph.

what Is the complexity(computational complexity) of graph isomorphism of 1.Complete graphs($K_n$) and 2.Utility graphs (Complete bipartite graphs ,$K_{n,n}$)? is it in polynomial ? Looks ...
1
vote
1answer
45 views

How to find that two adjacency matrices are equal

What is the easiest way to tell if these two graphs are isomorphic and how do I know which nodes in both graphs are the same. I've made the adjacency matrices but they are pretty big. I think I need ...
1
vote
1answer
28 views

Reducing Subgraph Isomorphism Complexity via an Enforced Layout of Nodes

This is my first question on the mathematics stack exchange. I hope my question is at least a little interesting, then. In any case, I was reading up on the subgraph isomorphism problem on wikipedia. ...