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

2
votes
1answer
65 views

isomorphism of graph definition

In Douglas West's book of graph theory, this is how isomorphism of graphs is defined. Please note that graphs need not be simple. An isomorphism from $G$ to $H$ is a bijection $f$ that maps $V(G)$ ...
2
votes
1answer
43 views

How can you show that 2 (adjacency) matrices are isomorphic?

Would you do it by showing that elementary matrix operations can be used to get from one matrix to the other? If not, how would you show that 2 adjacency matrices are isomorphic?
1
vote
1answer
54 views

Counting Graph Isomorphism

I am self studying graph theory and was wondering: is there a simple way to count/compute the number of subgraphs G that are isomorphic to another graph (say, G')? For instance, if G = the complete ...
1
vote
1answer
36 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 ...
0
votes
1answer
15 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
0
votes
1answer
19 views

What is an isomorphic graph (geometrical interpretation)?

I've seen definitions stating that "If $G=(V,E)$ and $G'=(V',E')$ , then a mapping $\theta : V \rightarrow V'$ is an isomorphism if, for all $u,v \in V$, $uv \in E$ if and only if $\theta (u) ...
0
votes
1answer
70 views

Do cycle graphs determine groups up to isomorphism?

This erroneous version of the wikipedia article for Cycle Graphs stated that the cycle graph of different groups could be the same. The immediate error is that it stated that the cycle graph of ...
0
votes
1answer
65 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
251 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.
4
votes
0answers
83 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. ...
2
votes
0answers
45 views

Are these graphs nonisomorphic?

I have got graph $G$ and graph $H$. My question is are these graphs isomorphic? I think no, because in graph $G$ vertex $v_{2}$ has four neighbours: $v_{1}$ with degree two $v_{8}$ with degree ...
2
votes
0answers
82 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) ...
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
70 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
50 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
0answers
17 views

Automorphism group of planar graphs

I am going through Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al. It has shown that the automorphism group of a planar graph $G$ is as follows. $$ \text{Aut} ...
1
vote
0answers
25 views

Not isomorphic graphs with same spectrum - exists?

I am wondering if there exists two graphs, which are not isomorphic with the condition that both of them have the same spectrum. Two graphs are isomorphic when they may be drawn in the same way. ...
1
vote
0answers
45 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other.

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Provide ...
1
vote
0answers
39 views

Is there a polynomial time algorithm for Poly-trees (oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
0answers
53 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
0answers
187 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
0answers
43 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 ...
0
votes
0answers
33 views

Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
0
votes
0answers
13 views

Murnaghan–Nakayama rule for order 2 subgroup of symmetric group

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In section 5, a scenario is presented as follows. Here, $G$ is the disjiont ...
0
votes
0answers
31 views

The size of the automorphism group of a graph

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et a. It is said on page 14 that the size of the automorphism group of a graph is either $1$ or ...
0
votes
0answers
51 views

NP algorithm to determine if two graphs are isomorphic

I have the following assignment on my Algorithms Analysis course. Given two undirected graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $\operatorname{card} (V_1) < \operatorname{card} (V_2)$ ...
0
votes
0answers
112 views

Counterexample for Algorithm of Isomorphism testing of Non-Symmetric Matrices

Claim: $E, F$ are non-symmetric 0-1 matrices of dimension $m \times n$ where $m>n$. Given $F \neq E$, it takes maximum maximum $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check ...
0
votes
0answers
21 views

On graph isomorphism

Consider two undirected graphs $G_1,G_2$ on $n$ vertices given by adjacencies $A,B\in\{0,1\}^{n\times n}$. We can also consider the adjacenies as biadjacencies of two bipartite graphs $B_1,B_2$. Is ...
0
votes
0answers
39 views

“List all non-isomorphic trees with exactly 6 vertices”

I've been given a question which asks me to "list all non-isomorphic trees with exactly 6 vertices". Whilst trying to work out how to tell whether a graph is isomorphic (which I still don't ...
0
votes
0answers
53 views

Nauty graph isomorphism weighted edges

I want to use sofeware Nauty version 2.5 to check if edge-weighted graphs are isomorphic to each other. However weighted edge is not supported by Nauty. Professor McKay mentioned that there's an ...
0
votes
0answers
99 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 ...