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

1
vote
1answer
44 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
54 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$ ...
2
votes
1answer
64 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 ...
0
votes
1answer
18 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
49 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 ...
2
votes
1answer
96 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 ...
0
votes
1answer
55 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
22 views

Draw all non-isomorph graphs with 7 knots

in our course we had to draw all non-isomorph graphs with 7 knots without loops. Since this is hard to explain I'll add an Image. The blue written part is accepted by the tutor and the pencil ...
0
votes
0answers
33 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
1answer
42 views

What is Graph Isomorphism and Graph Invariant?

While I was reading Reinhard Diestel text on graphs, I came across this paragraph. Let G = (V, E) and G' = (V' , E' ) be two graphs. We call G and G' isomorphic,and write G $\simeq $ G' , if ...
1
vote
0answers
23 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 ...
3
votes
1answer
65 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) ...
8
votes
2answers
309 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$ ...
2
votes
1answer
17 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$ ...
1
vote
1answer
37 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 ...
0
votes
2answers
46 views

Why are these two graphs isomorphic?

I have the following graphs and I am trying to identify if they are isomorphic or not. The solutions that I have indicate they are isomorphic, with the following bijection: However, it appears ...
4
votes
0answers
49 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
3answers
71 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
1answer
49 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
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
46 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 ...
1
vote
1answer
27 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. ...
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
1answer
50 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 ...
0
votes
0answers
25 views

Isomorphism testing for minimal SP-trees

I'm doing a bit of research on the SP-trees. I'm still new to this whole problematic, so I'd be thankful if someone cleared this thing up. :) This is the scenario that I'm trying to come up with a ...
-2
votes
3answers
136 views

Graph isomorphism when all vertices have the same degree

Are 2 connected graphs isomorphic if they have the same number of vertices and each vertex has the same degree $k$? I don't know how to prove it but I also can't find a counter example.
0
votes
1answer
94 views

How many nonisomorphic graphs are there with 10 vertices and 43 edges?

How would I go about solving this? I know that $K_{10}$ has $9+8+7+\dots+1=45$ edges. So would it be something like $\binom {45}{43}$ because out of the 45 total edges, one must choose 43 for the ...
3
votes
1answer
63 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 ...
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?
0
votes
0answers
75 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 ...
1
vote
1answer
250 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 ...
0
votes
1answer
64 views

Is the number of simple circuits of a particular length preserved in two isomorphic graphs?

If two graphs are isomorphic, and one has a simple circuit of a particular length, must the other graph also have a circuit of the same length? Do they also have to have the same number of such ...
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?
0
votes
2answers
43 views

Concept: The graph component

I have the following definition for a Component of a graph: A subgraph $H$ of a graph $G$ is a component of $G$ if $H$ is a maximal connected subgraph of $G$, ...
0
votes
1answer
70 views

Any two abelian group of order 8 must be isomorphic

TRUE/FALSE :Any two abelian group of order 8 must be isomorphic SOLUTION: True The problem of finding all abelian groups of order 8 is impossible to solve, because there are infinitely many ...
1
vote
1answer
46 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 ...
0
votes
1answer
68 views

Proving two graphs are isomorphic in polynomial time - Bondy/Murty - Graph Theory Page 6

I am trying to do the below problem: Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since it is $3\text{-regular}$. I ...
0
votes
1answer
60 views

Proof verification: (Pretty pictures :) )Showing two graphs are not isomorphic. Bondy/Murty - Graph theory Page 5

I want to show the below two graphs are not isomorphic. Treat the left as graph $\bf G$ and the right as graph $\bf H$. $\bf G$ and $\bf H$ are not isomorhpic: Although we have a bijective mapping ...
1
vote
3answers
124 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?
0
votes
1answer
39 views

How can I show complete graphs are determined by spectrum?

I understand how to prove a complete graph $K_n$ has spectrum $\lbrace -1^{(n-1)},n-1 \rbrace$. However I am having difficulty proving that the spectrum uniquely determines the complete graph. ...
1
vote
1answer
52 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
25 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
53 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
2answers
145 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
0answers
38 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) ...
0
votes
1answer
46 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
137 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.
0
votes
1answer
65 views

Graph isomorphism problem for labeled graphs

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
1
vote
1answer
89 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 ...
2
votes
0answers
41 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$ ...