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
64 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
95 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 ...
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 ...
1
vote
1answer
23 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
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 ...
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
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 ...
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
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 ...
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$ ...
1
vote
0answers
22 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
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) ...
1
vote
0answers
168 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
38 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

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