# Tagged Questions

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$.

8k 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, ...
2k 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 ...
23k 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 proven. ...
408 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$ ...
291 views

### Is there any algorithm to find Isomorphism function between two graphs?

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a ...
512 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.
61 views

### What makes graph automorphisms interesting?

I've completed a short course on graph theory and we never studied graph isomorphisms in depth, but I've seen at least a bit of this covered in most graph theory books I've grabbed, that grabbed my ...
164 views

### How Graph Isomorphism is used to determine Graph Automorphism?

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage- For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes ...
44 views

### How to detect automorphism of union of graphs?

On page 1 of Lecture 2, Algebra and Computation , (Course Instructor: V. Arvind), there is a theorem- Theorem 2. With Graph − Iso (graph isomorphism) as an oracle, there is a polynomial time ...
60 views

### Is distance between two graphs defined somehow?

If the two graphs are isomorphic, then their distance is zero. And this distance increases, if vertices or edges are added or removed to/from one of the graphs. Does this "distance" have a special ...
29 views

### What is the meaning of saying “two graph vertices are in correspondence?”

What are the conditions for two graphs to be in correspondence? I know for isomorphic - Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. ...
85 views

### Colored graph isomorphism reduction to uncolored graph isomorphism

I am trying to find a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism. Doing a search on this problem, I found this article and it seems like theorem 1 is ...
94 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. ...
249 views

### Isomorphic graphs

I was wondering if this solution for finding wheter or not two graphs are isomorphic would work: I claim that two graphs are isomorphic if their degree list coincide. For example let's say that I ...
7k 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 ...
68 views

### Two graphs that are not isomorphic?

They have the same number of vertices and edges. The degree sequences are the same (5,4,4,4,4,4,3). Looking at each vertex of degree i, they have edges to vertices of the same degrees in each graph. I'...
96 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 ...
288 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) (...
181 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 ...
73 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 ...
32 views

### when do we say if two graphs are isomorphic and when do we say they are the same?

A complete graph of 4 vertices can be represented with a square and also with a triangle with a vertex in the middle. I'm confused if I should call the two graphs isomorphic or the same? Also, can ...
6k 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 ...
608 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 ...
134 views

### One to One correspondence between vertices of two graphs?

Is it necessary that in two undirected graphs if we need to prove that vertices have one to one correspondence then graph should have same number of edges? What about same number of degree? Can ...
47 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 ...
69 views

58 views

### Number of Labels used in reduction of Isomorphism of Labelled Graph to Graph Isomorphism

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the ...
63 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.
109 views

### The set of isomorphisms from a right coset of the automorphism group $Aut(X)$ in $S_n$.

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , on page 22- Theorem 4 Let $X$ and $X'$ be two isomorphic graphs with vertex set $V = \{1 ..... n\}$ , Then the set of ...
32 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$ ...
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 ... 1answer 308 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 ... 1answer 42 views ### Are two graphs isomorphic if there is a bijective distance-preserving map between them? Suppose that there exist two connected graphs G and H and a one-to-one function \varphi from the vertex set V(G) onto V(H) such that the distance \operatorname d_G(u, v) = \operatorname d_H(... 1answer 262 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, ... 4answers 293 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? 2answers 72 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 ... 2answers 209 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 ... 0answers 34 views ### Automorphism and Direct Product of Generating Set Notation: H  are partitioned into sub-graphs  H_1,H_2 \cdots H_x . We see them in the adjacency matrix of H given below-$$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-...
Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume $H$ has subgraphs $H_1, H_2... H_x$ (total $x$ vertex set). ...