0
votes
1answer
23 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
0answers
23 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$ ...
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
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
103 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 ...
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. ...
0
votes
3answers
116 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
54 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 ...
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
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
682 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
42 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
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 ...
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
118 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 ...
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
77 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
32 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.
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
193 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
58 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 ...
1
vote
1answer
83 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 ...
7
votes
2answers
183 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.
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, ...
2
votes
1answer
287 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 ...
1
vote
0answers
36 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
379 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.
3
votes
2answers
154 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) ...
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. *----------* /|\ | | | | ...
1
vote
1answer
205 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
223 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 ...