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

0
votes
2answers
48 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 ...
2
votes
1answer
270 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 ...
0
votes
1answer
28 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
0answers
35 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
32 views

Zero knowledge proof for graph isomorphism

Consider the following algorithm: Input: pair of graphs $(G,G')$ with vertex set $\{1,2,3,...,n\}$ Output: accepts if $G$ is not isomorphic to $G'$ and rejects otherwise (with small ...
0
votes
0answers
43 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
0answers
52 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^{**}$?
0
votes
0answers
33 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 ...