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

81 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)$ ...
61 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?
64 views

### How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
55 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 ...
60 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 run-times/...
44 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 ...
16 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 ...
24 views

71 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 ...
295 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.
18 views

### labelled graph characteristic polynomial

Given the adjacency matrix $\mathbf{A}$ for a simple connected graph, the characteristic polynomial is defined as: $$p(\lambda) = \det(\lambda \mathbf{I} - \mathbf{A})$$ Now if an edge between ...
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. ...
40 views

### Isomorphism of Non-Symmetric Matrix when Permutation-Set is given: A simple observation

Context: Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not ...
34 views

35 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. ...
61 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 ...
42 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 ...
57 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) ...
206 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^{**}$?
46 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 ...
20 views

### Is there a name for these permutations?

Given adjacency matrix $A$ of a graph is there a name for permutations $P$ such that $A=PAP'$? Is this an automrphic permutation?
31 views

### If graph isomorphism yields a polynomial time algorihtm.

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
18 views

### Vertex-transitivity of the automorphism group of a digraph

I am trying to understand the theorem 3 of Cycles in graphs and groups by Kantor. Theorem $3$ If $G$ is a vertex-transitive group of automorphisms of a digraph $\Gamma$ with outdegree $d \ge 1$, ...
26 views

### Isomorphism between a Cartesian plane and its rescaled version

Definition. Let $M$ be a model of Neutral Geometry and $t > 0$ a positive real number. The rescaled model $M_t$ is defined as follows: • The points of $M_t$ are the same as those of $M$; • The ...
37 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$. ...
17 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 ...
35 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 $2$...
58 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)$ ...
129 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 ...
24 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 ...
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 ...