Questions tagged [graph-isomorphism]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
39 views

Finding an isomorphism between an infinite tree and a subgraph of $\mathbb{Z}^3$

I was wondering if there exists a construction of an infinite tree, with some properties, that is isomorphic to subgraph of $\mathbb{Z}^3$. Notation Let $\Gamma_n$ denote the tree's vertices at ...
user avatar
  • 1,956
0 votes
1 answer
34 views

Are two graphs isomorphic if: every spanning tree of one graph is isomorphic to some spanning tree of the other, and vice versa? [closed]

Let $G_1,G_2$ denote two simple graphs, and $T_1,T_2$ denote their respective set of all spanning trees. Are $G_1,G_2$ isomorphic if every $t \in T_i$ is isomorphic to some $t' \in T_j$ for both $i,j \...
user avatar
  • 135
0 votes
0 answers
25 views

What families of graphs is the subgraph isomorphism problem known to remain NP-complete?

The subgraph isomorphism problem consists of two graphs, G and H and asks if there is some subgraph of G that is isomorphic to H. There are several families that H can be sampled from that preserve ...
user avatar
1 vote
1 answer
37 views

Number of pairwise non isomorphic 2-connected graph with no $K_4^-$ minor

I had this question in my graph theory exam today, and I'm pretty sure I answered it wrong. We define $K_4^-$ as $K_4$ with one less edge. Find the number of pairwise non isomorphic graphs $G$, such ...
user avatar
1 vote
2 answers
94 views

Why aren't the eigenvectors of a graph's adjacency matrix useful for the graph isomorphism problem?

I know eigenvalues of a graph's adjacency matrix are very heavily studied because of their relationship to the structure of the graph, but how come no one studies the eigenvectors? Even if they don't ...
user avatar
  • 384
1 vote
1 answer
65 views

Sufficient condition for a non-empty intersection of two graph automorphism sets

I hope the title wasn't confusing because I wasn't able to summarize it without providing the details. The problem I'm trying to solve is the following: We are given a graph $G=(V,E)$ We know that it ...
user avatar
  • 11
1 vote
1 answer
42 views

Are the distributions of uniform spanning trees unique up to graph isomorphism?

I've tried to find any publications on this unsuccessfully, but maybe someone here has some ideas where to look. Consider a directed graph $G = (V_G, A_G)$ of $N$ nodes and $M$ edges. Let $T_{N}$ ...
user avatar
  • 15
0 votes
1 answer
70 views

The sufficient way to show a homomorphism is well-defined.

I was reading a solution of a linear algebra (or Euclid Geometry) problem which asks to show that dihedral group $D_n$ of order $2n$ is isomorphic to the group $G=\left<a,b\right>$ s.t $a^2=e, \...
user avatar
  • 1,248
2 votes
1 answer
62 views

How to prove that the 2 graph matrices describe the same graph?

To simplify the question, we suppose that: All verticles of $G$ are $v_1, v_2,...,v_n$ There is no edge which connect it with itself. $G$ is non-directed. There are at most one edge between 2 ...
user avatar
0 votes
1 answer
46 views

Shouldn't any relabelling of vertices in a graph preserve isomorphism?

Say $G$ and $H$ are two isomorphic graphs. There is the following theorem: Two simple graphs $G$ and $H$ are isomorphic if and only if there exists a permutation matrix $P$ such that $A_G=PA_HP^t$. ...
user avatar
  • 1,849
0 votes
0 answers
39 views

Isomorphy between graphs

I am asked to find a undirected graph that is Isomorphic to a directed graph. Does that even make sense? directed graph with 3 nodes My first thought was a cycle with 3 Vertices, but I don't feel ...
user avatar
0 votes
1 answer
67 views

How many graphs on [$n$] vertices are isomorphic to $K_n$

Total Number of Graphs on a vertex set $[n]$ = $2^{\binom{n}{2}}$ Since the total number of isomorphisms is equivalent to total number of bijection $\implies$ $n!$ What it would tell if divide these ...
user avatar
0 votes
1 answer
53 views

What kind of graph coloring is this?

Assume a very simple graph with 3 points: V0—V1—V2 The following represent all the different possible colorings using 3 colors. I’ve labelled all of the types of colorings that are isomorphic (is that ...
user avatar
  • 155
2 votes
1 answer
22 views

Relationship between the sizes of orbits of nodes

About a year and a half ago I wrote a certain proposition offhand in a proof. I must have thought it was trivial at the time and so did not prove it, but months later it is not quite so trivial to me ...
user avatar
  • 1,295
1 vote
1 answer
68 views

The Diameter of resulting graph by sum of two unions.

Let's say we have a graph $T$, which is also a spanning tree of a graph $G$, $T$ is connected, now let's say the diameter of $T$ is $x$. Now, what would be the diameter of : $$ (T \cup T^c) + (T \cup ...
user avatar
1 vote
1 answer
58 views

How to determine whether two graphs are isomorphic from larger adjacency matrices

Determine whether the two graphs $G$ and $G'$ are isomorphic given their adjacency matrices: $$G=\left[\begin{array}{llllllll} 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 &...
user avatar
  • 31
0 votes
1 answer
36 views

Show that a bijective function $f: V \to V^{'}$ is an isomorphism from graph $G$ to graph $G^{\ '}$

I have to show the following: For the case that someone uses other definitions: $V$ is the set of the vertices of $G$ $E$ is the set of $2$-element subsets of $V$ defined as $E \subseteq {V \choose ...
user avatar
  • 166
1 vote
1 answer
41 views

What is the most unambiguous digraph representation of NAND/NOR?

Is there an official or standardized way to represent the basic boolean operations with directed graphs? (I don't mean like in circuit diagrams.) If so, what is it? And if not, I would also accept an ...
user avatar
  • 4,941
0 votes
0 answers
13 views

build random multigraphs with multiple edges but no self loops with given node degree

I have a given graph with associated node degrees [23,100,1225,40....n]. My aim is to randomise graph generation based on node degree of my graph but without self-loops. Multiple edges are allowed. My ...
user avatar
8 votes
2 answers
238 views

Is a graph determined by its multiset of spanning trees?

Is it known whether a (connected) graph is determined by its multiset of spanning trees? In other words, do any two non-isomorphic connected graphs have different multisets of spanning trees? By a ...
user avatar
  • 387
0 votes
0 answers
72 views

Draw a pair of NON isomorphic graphs with same no. of vertices, same degree sequence and same cycle lengths.

I'm very new to graph theory and I've been struggling with this question because while I can come up with an example with the same degree sequence, I'm not sure how it's possible with the same cycle ...
user avatar
  • 1
1 vote
1 answer
67 views

Directed graph isomorphism condition correctness

I'm currently working on a project and I've hit a bit of a stumbling point regarding one part related to directed graph isomorphism. To put it short, I have to find all graphs with N = 1,2,3,4 ...
user avatar
  • 13
0 votes
1 answer
89 views

Given this theorem, Why is Subgraph Isomorphism NP hard and not polynomial?

So, I read the following Theorem by Matousek and Thomas: Given graphs $G$ and $H$, we want to check if there is a subgraph $S \subseteq H$ such that $S$ and $G$ are isomorphic. Then, if the maximum ...
user avatar
1 vote
2 answers
77 views

Pairwise Non Isomorphic 3-regular Graphs of certain orders

I am currently reviewing some graph theory before an exam and ran into the following problem which has me fairly stumped. The number of pairwise non-isomorphic 3-regular graphs of order 8 is 6, the ...
user avatar
4 votes
2 answers
207 views

Which Pair of these 3 graphs are is isomorphic

I know that the 3 graphs have the same number of vertices and edges which is one of the condition for isomorphism . And I also know that having the same number of vertices and edges does not mean that ...
user avatar
1 vote
1 answer
128 views

Measure similarity between isomorphic graphs with different node labels

I am using graphs to represent some structured data. In my case, I have a time series of undirected unweighted graphs with the same topology (i.e. isomorphic graphs with same number of nodes and edges,...
user avatar
1 vote
1 answer
95 views

Certifier in the subgraph isomorphism problem

In the subgraph isomorphism problem we need to establish a certifier where we can map the edges from induced map to the original map. And it will take polynomial time to achieve. Does this mean that ...
user avatar
0 votes
0 answers
56 views

Prove: The Induced Homomorphism $\pi_r$ of E. M. Luks

Let $X$ be a trivalent graph. We denote by ${\rm Aut}_e(X)$ the subgroup of ${\rm Aut}(X)$ such as fix the edge $e$. Here $X_r$ is the subgraph consisting of all vertices and all edges of the graph$X$ ...
user avatar
0 votes
0 answers
41 views

Graph isomorphism from equivalence relation

I know that any graph isomorphism defines an equivalence relation on said graph. But now I have some equivalence relation on a graph. Is it possible to construct an isomorphism? Intuitively I would ...
user avatar
  • 955
2 votes
0 answers
52 views

Choosing a Group for Graph Isomorphism [duplicate]

I am trying to figure out how Luks' graph isomorphism algorithm works, I understand the clear answer given by Misha Lavrov about trivalent graph isomorphism, it basically says: Construct graph $Z$ by ...
user avatar
2 votes
0 answers
40 views

Are all Kn graphs -1 edge isomorphic?

Basically what the title says: Are all complete graphs with a missing edge the same graph? I think they are and I know my question is very simple ,yet, I only now begun getting involved in ...
user avatar
3 votes
1 answer
77 views

Is there a simpler way to prove these graphs are non-isomorphic?

The graphs My solution Graphs $\mathcal{G}$ and $\mathcal{H}$ have the same number of edges, vertices and the same degree sequence. They also have the same number of 3-cycles. I proved they are not ...
user avatar
0 votes
1 answer
69 views

Orbits in a Graph for Transitive Action

Let $X$ and $Y$ be bipartite graphs over the same set of vertices $V = V_1\cup V_2$. Let $E(X)$ and $E(Y )$ denote the set of edges of $X$ and $Y$, respectively. Isomorphisms of $X$ and $Y$ $\textbf{...
user avatar
0 votes
1 answer
39 views

Cycle Decomposition as Colored-Edges? How?

In a proposition of graph isomorphism I find that for a generator $σ \in S$ (the set of generator of a group), edges can be added to a directed edge-colored graph $X(G)$ of color $σ$ corresponding to ...
user avatar
1 vote
1 answer
116 views

How can I label vertices of the graph, so they are the same as on the other labeled graph?

Is there some algorithm to label equivalent vertices of unlabeled graph? For example, suppose I have two distinct graphs $G_1$ and $G_2$, and they are isomorophic. However, $G_1$ has labeled vertices ...
user avatar
0 votes
0 answers
28 views

How to create a special graph?

I wish to generate an undirected lattice graph $G$ with following features: It has $m\times n$ vertexes; Each vertex has only two kinds of labels ($0$ or $1$); Every $t\times t$ subgraph is unique. ...
user avatar
0 votes
0 answers
36 views

For two graphs to be isomorphic should the set of vertices be the same?

We have three persons $P_1, P_2$ and $P_3$. $P_1$ is the father of $P_2$ and $P_3$ is the wife of $P_2$. I am making two graphs with edges edges representing the relation. Say I have one graph $G_1$ ...
user avatar
1 vote
1 answer
156 views

Isomorphism classes of trees with maximum degree $3$ and $6$ vertices

List the isomorphism classes of trees with maximum degree $3$ and $6$ vertices. I start with the star $K_{1,3}$ and append vertices accordingly to achieve $6$ vertices keeping maximum degree $3$. I ...
user avatar
  • 1,246
0 votes
0 answers
17 views

what does $1/n$ times the expected number of edges per vertex in a finite poset on $n$ points approach as $n$ goes to infinity?

Let $S_n$ be a maximal set of inequivalent posets on $n$ points (i.e., one with maximum possible cardinality). Let $E_n$ be the total number of edges in $S_n.$ Clearly $|S_n|$ and $|E_n|$ depend only ...
user avatar
0 votes
1 answer
27 views

Tree isomorphism

I'm trying make a proof for this statement : $T=(V;E)$ is a tree, if $f,g$ are two isomorphism of T such that for each leaves $u \in T$ we have $f(u)=g(u)$ then $f=g$ I can imagine how this is true ...
user avatar
  • 23
0 votes
1 answer
59 views

Is equivalent labelling enough to prove isomorphism between two graphs?

Determine whether the following graphs are isomorphic. Labelling vertices of both graphs as $u_1,u_2,u_3,u_4,v_1,v_2,v_3,v_4$ in the order given above, we see that these graphs are bipartite with $...
user avatar
  • 1,246
0 votes
0 answers
28 views

Determine isomorphism classes for pairs of families from paths, cycles and bipartite graphs

Consider the family of graphs $A=\{\text{paths}\}$, $B=\{\text{cycles}\}$ and $D=\{\text{bipartite graphs}\}$. For each pair of these families, determine all isomorphism classes of graphs that belong ...
user avatar
  • 1,246
0 votes
0 answers
32 views

"Let $G \cong H$. $G$ is planar graph $\Leftrightarrow$ $H$ is planar graph."

"Let $G \cong H$. In this case $G$ is planar graph $\Leftrightarrow$ $H$ is planar graph." If this proposition true, prove that. If false, give an example. This question in my exercise book. ...
user avatar
0 votes
1 answer
66 views

Determine if the two graphs are isomorphic

Let G be the graph with vertex and edge sets $$V = \{1, 2, 3, 4\}$$ and $$E = \{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$$ and H be the graph with vertex and edge sets $$V = \{a, b, c, d\} $$and $$E =...
user avatar
1 vote
1 answer
206 views

Is there a way to know how many non-isomorphic spanning trees there are for a graph?

I have a big doubt: Is there a way to know how many non-isomorphic spanning trees there are for a graph? In a Spanning Tree there are no cycles, one less thing to worry about.
user avatar
0 votes
1 answer
37 views

Unsure of graph isomorphism

Are the following sets of graphs isomorphic? I believe the first set (the rooted trees) are, and with the second set (the free trees), I notice that both trees have 2 vertices with degree 3, one with ...
user avatar
  • 1
1 vote
1 answer
170 views

Graphs with same degree sequence and same number of vertices isomorphic? [duplicate]

if there are two graph $G$ and $H$ that have same number of vertices, and their degree sequences are the same. Does this mean that they are isomorphic ?
user avatar
1 vote
0 answers
164 views

Dual of dual of planar graph $G$ is isomorphic to $G$ if and only if $G$ is connected.

I have been asked to show that the dual of the dual, $(G^*)^*$, of a planar graph $G$ is isomorphic to $G$ if and only if $G$ is connected. I understand the reasoning in the answer one but that cannot ...
user avatar
0 votes
0 answers
32 views

Maximal number of edges

Given a simple graph on 15 vertices consists of several (more than one) isomorphic connected components. What is the maximal possible number of edges in this graph? I tried by using the bipartite ...
user avatar
  • 187
1 vote
1 answer
93 views

Unique four-regular, simple planar graph such that every face is bounded by three edges

A question on my graph theory exam asked us to find how many $4$-regular, simple planar graphs there are up to isomorphism such that every face, including the outer face, is bounded by three edges. I ...
user avatar
  • 3,387

1
2 3 4 5
9