Graph Operations
See also the parameters page
There’s a lot of fun things to do with graphs! Ways to combine them, or break them apart, or simplify them or make them more complex. And then there’s parameters: numbers that quantify something “easy” or “hard” or “big” about the graph, that may or may not play nicely with these operations. And finally, we can run algorithms on graphs, and the runtimes of these algorithms may or may not play nicely with structural changes. This page is my place to collect facts about relative comes of substructure. It’s far too disorganized to put anywhere else, but if you ended up here, I hope you get something useful or at least interesting out of it. 😃
Some useful pages elsewhere: 1 2 3
This page is focused on statements about unlabelled, simple graphs. Selfedges may be allowed, those are discussed in the relevant parts. A lack of labelling means that some operations (e.g. zigzag products) don’t apply.
Binary graph operations
These are operations that combine two graphs into a larger one. The table also describes how the number of vertices and edges grows; whether the operation is commutative and/or associative; what the identity graph is; and then, later maybe, some information about how it affects graph properties. We call our input graphs G1
and G2
, and say they have V1
/E1
and V2
/E2
vertices and edges, respectively. In the “Identity” column, B1
refers to the singlevertex Bouquet: a single selfloop.
Operation  Notation/Description  V(f(G,H))  E(f(G,H))  Com.  Ass.  Id 

Productlike  
Cartesian Product  G1□G2 
V1*V2 
V1*E2 + V2*E1 
✅  ✅  K1 
Tensor Product^{1}  G1⨯G2 
V1*V2 
2*E1*E2 
✅  ✅  B1 ^{2} 
Strong Product  G1⊠G2 Union of G1□G2 and G1⨯G2 . 
V1*V2 
V1*E2 + V2*E1 + 2*E1*E2 
✅  ✅  K1 
Conormal Product  No standard notation Union of G1[G2] and G2[G1] 
V1*V2 
E2*V1^2 + E1*V2^2  2*E1*E2 
✅  ✅  K1 
Modular Product  No standard notation Union of G1⨯G2 and G̅1⨯G̅2 
V1*V2 
E1*E2 + ((V1^2V1)/2E1)*((V2^2V2)/2E2) 
✅  ✅  B1 ^{2} 
Lexicographical Product^{3}  G1[G2] 
V1 * V2 
V1*E2 + E1*V2^2 
❌  ✅  K1 /K1 ^{4} 
Homomorphic Product  G1⋉G2 
V1*V2 
V1*(V2^2V2)/2 + E1*V2^2  2*E1*E2 
❌  ❌  ❌/K1 ^{5} 
Corona Product  G1○G2 
V1*(1+V2) 
E1 + V1*E2 + V1*V2 
❌  ❌  ❌/K0 ^{6} 
Sumlike  
Disjoint Union^{7}  G1+G2 or G1⊕G2 
V1 + V2 
E1 + E2 
✅  ✅  K0 
Graph Join  No standard notation Comp(G̅1⊕G̅2) 
V1 + V2 
E1 + E2 + V1*V2 
✅  ✅  K0 
Somewhat notable operations absent from this list include the rooted product, zigzag product, replacement product, seriesparallel composition, and the Hajós construction which require other “information” about the graphs, or only apply to certain graphs.
Unary Graph Operations
Simple ways to alter a graph. These are “nonspecific”: they take a graph and give a graph out. Other actions that target a specific spot, like “trim away a degree zero vertex” or DeltaWye transformations or vertex contraction, are in the next section.
Operation  V  E  Notes 

Vertex addition  V+1  E  
Universal neighbor addition  V+1  E+V  Add a vertex neighboring everything else. 
Complement  V  V*(V1)/2  E 

Line graph  E  ((sum of d^2)V)/2 

Mycielskian  2V+1 
3E+V 

Double graph  2V 
4E 

Bipartite double^{8}  2V 
2E 

Graph square  V   
Modifications
These are moderately “atomic” actions that act a single location. They are defined here primarily so that we can then discus which other things respect these modifications: for instance, “H is a subgraph of G” respect edge deletion on H, but not edge contraction. If you replace “subgraph” with “induced subgraph”, then edge deletion is no longer compatible; if you use “minor”, then edge contraction is also compatible.
Operation  Targets a …  Description  Notes 

Vertex deletion  Vertex  Remove a vertex from the graph, and all edges using that vertex  
Edge deletion  Edge  Remove an edge from a graph  
Dissolution^{9}  Degree2 vertex  Given a degree2 vertex u with neighbors v and w, remove u and add an edge (v,w).  If working in a setting where loops are allowed: u cannot have a loop. In a setting where multiedges are allowed: if v and w are neighbors, then this creates a multiedge. If v=w, then dissolution creates a loop at v. As a consequence, if multiedges are allowed and loops aren’t allowed, and v=w, then u cannot be dissolved. 
Subdivision^{10}  Edge  Given an edge (v,w), remove that edge, create a new vertex u, and add edges (v,u) and (u,w).  Dissolution is the inverse operation to subdivision. 
Vertex Identification  Two vertices  Given two distinct vertices u and v, delete v. For each edge (v,w) that was deleted, add a new edge (u,w)  If loops are allowed: this creates a loop if u and v are neighbors. If multiedges are allowed: this can create multiedges where there previously were none, if u and v had neighbors in common. 
Contraction  Edge  The same as vertex identification, but restricted to the case where u and v are neighbors. It differs in that, even if loops are allowed, no loop is created.  
Lifting  P_3 ^{11} 
If there is an edge (u,v) and another edge (v,w), then remove these two edges from the graph and add an edge (u,w).  Lifting and vertex deletion together can effect dissolution. 
Multiedge simplification  Multiedge  If there are multiple edges (u,v), then remove one of them.  Special case of edge deletion. Obviously only applies in settings where multiedges are allowed. 
Loop simplification  Loop  Remove a loop.  Special case of edge deletion. Obviously only applies in settings where loops are allowed. 
YΔ  Degree3 vertex  Remove u with neighbors v, w, and x. Add edges (v,w), (v,x), and (w,x).  Inverse of ΔY 
ΔY  Triangle  Remove the edges (v,w), (v,x) and (w,x), add a new vertex u, and add edges (u,v), (u,w), (u,x).  Inverse of YΔ, exept that in settings without multiedges this can lose edges that were “doubled up” during the YΔ. 
Detwinning  Twin pair  Given a pair of true twins^{12} u and v, delete v. 
Graph Substructures
There are a lot of different ways to say that a graph G “contains a copy” of H. The strictest notion is that of graph isomorphism: G and H must identical, up to a relabelling of vertices. Other substructure relationships are typically defined in one of two ways.
The first is by modifications. We would say that G contains H if we can follow a list of permitted operations on G to eventually reach a graph isomorphic with H. (Dually, we could give allowed operations to grow H into G.) For example, “induced subgraph” is defined by vertex deletions, while “subgraph” also allows edge deletions.
The second way to define a substructure by a mapping. There we would say that G contains H if there’s a map $f_V : V(H) \to V(G)$, and possibly a map for $f_E$ as well, obeying some kind of morphismlike condition. For example, “subgraph” is defined by injective maps f_{V} that preserve adjacency. “Induced subgraph” requires that f_{V} also preserves nonadjacency. Where possible, this table tries to describe substructure both ways. It may be necessary that f_{V} maps a vertex in H to a whole set of vertices in G, or vice versa, or likewise for f_{E}.
For each notion of substructure, one key aspect is its order structure: does it obey the descending chain condition (or the ascending chain condition)? Is it well quasi ordered? Is it, in fact, an equivalence class? These get their own columns, with an ❌ or ✅. For those with an ❌, a comment like K_n
means that the complete graphs form a counterexample^{13}.
The last question is, how computationally difficult is to recognize inclusion? We can allow H to vary with G, in which case aim for a categorization as P
, NPC
, or GIC
^{14}. If we hold H fixed with k
many vertices, then we aim to categorize as FPT
, W[1]C
, XP
, or paraNPC
^{15}. I write that a class is “trivially FPT” if it runs in time f(k)*O(1)
, usually because there are only finitely many graphs that any H can embed in (as is the case with graph isomorphism). Again, we try to give an obvious class exhibiting the difficulty^{16} if possible, or if not, a reference.
Name  Operations  Map $f_V : H \to G$  DCC  ACC  WQO  Equiv  Complexity  Parameterized 

Graph Isomorphism  None  $u\sim v \iff f(u) \sim f(v)$ f_{V} bijective 
✅  ✅  ❌ $K_n$ 
✅  GIC  trivially FPT Fixed vertex count 
Induced Subgraph^{17}  Vertex deletion  $u\sim v \iff f(u) \sim f(v)$ f_{V} injective 
✅  ❌ $K_n$ 
❌ Ref. $C_n$ 
❌  NPC $K_n$, Maxclique 
W[1]C $K_n$ 
Subgraph  Vertex deletion Edge deletion 
$u\sim v \implies f(u) \sim f(v)$ f_{V} injective 
✅  ❌ $K_n$ 
❌ Ref. $C_n$ 
❌  NPC $K_n$, Maxclique 
W[1]C $K_n$ 
Spanning Subgraph  Edge deletion  $u\sim v \implies f(u) \sim f(v)$ f_{V} bijective 
✅  ✅  ❌ $C_n$ 
❌  NPC $C_n$, Hamiltonian cycle 
trivially FPT Fixed vertex count 
Dissolution^{18}  Dissolution  $f_V$ injective $f_E$ takes edges in H to degree2 paths in G $f_E$ bijective 
✅  ❌ $K_n$ 
❌ $K_n$ 
❌  NPC ^{19} 
FPT^{20} 
Homeomorphism  Dissolution Subdivision 
$f_V$ bijects vertices of degree not 2 $f_E$ takes degree2 paths in H to degree2 paths in G $f_E$ bijective 
✅  ✅  ❌ $K_n$ 
✅  GIC^{21}  FPT^{20} 
Minor  Vertex deletion Edge deleition Contraction 
f  ✅  ❌ $K_n$ 
✅  ❌  NPC $C_n$, Hamiltonian cycle 
FPT 
Topological Minor^{22}  Vertex deletion Edge deletion Dissolution 
f  ✅  ❌ $K_n$ 
❌ Ref.  ❌  NPC $C_n$, Hamiltonian cycle 
FPT 
Induced Minor  Vertex deletion Contraction 
f  ✅  ❌ $K_n$ 
❌ Ref.  ❌  NPC $C_n$, Hamiltonian cycle 
Open? (2012) 
Induced Topological Minor  Vertex deletion Dissolution 
f  ✅  ❌ $K_n$ 
❌^{23}  ❌  NPC $C_n$, Hamiltonian cycle 
p 
Contraction Minor  Contraction  f  ✅  ❌  ❌ Ref.  ❌  NPC  This claims it’s open as of 2012. This claims it’s NP hard even when $V(H)=4$. 
Immersion Minor^{24}  Vertex deletion Edge deletion Lifting 
$f_V$ injective $f_E$ takes edges in H to edgedisjoint paths in G 
d  a  w  ❌  c  FPT 
Induced Immersion  Vertex deletion Lifting (No multiedge deletion!) 
$f_V$ injective $f_E$ takes edges in H to edgedisjoint paths in G $f_E$ bijective on the $E(\textrm{image of }f_V)$ 
d  a  w  ❌  NPC $C_n$^{25} 
XP 
W[1] hard? FPT? 

Weak Immersion  Vertex deletion Edge deletion Lifting Subdivision (Multiedges? Dissolution?) 
f  d  a  w  ❌  c  p 
Strong Immersion  o  f  d  a  w  ❌  c  p 
Homomorphism  Vertex identification vertex addition Edge addition Multiedge simplification (No selfloop deletion!) 
$u\sim v \implies f(u) \sim f(v)$ f_{V} may be manytoone 
d  a  w  ❌  c  p 
Homomorphic Equivalence  o  Homomorphism from G to H Homomorphism from H to G 
d  a  w  ✅  c  p 
Faithful Homomorphism  o  $u\sim v \implies f(u) \sim f(v)$ $f(u) \sim f(v) \implies \exists x,y: x\sim y \wedge f(x)=f(u) \wedge f(y)=f(v)$^{26} f_{V} may be manytoone 
d  a  w  ❌  c  p 
Full Homomorphism^{27}  o  $u\sim v \implies f(u) \sim f(v)$ $u \not\sim y \implies f(u) \not\sim f(v)$ f_{V} may be manytoone 
d  a  w  ❌  c  p 
Epimorphism^{28}  Vertex identification Edge addition Multiedge simplification (No selfloop deletion!) 
f  d  a  w  ❌  c  p 
Monomorphism^{29}  Vertex addition Edge addition Multiedge simplification (No selfloop deletion!) 
f  d  a  w  ❌  c  p 
TODO: There’s restricted immersion minors which are like immersion minors but preserve planarity in interesting ways, by restricting which contractions are “admissible”. They also define coimmersion minors based on a new operation called constriction; and accordingly, restricted coimmersion minors. They were all inspired by the bipartite minors, which involve peripheral cycles as an alternate form admissibility. This work also mentions the action of suppressing a vertex, which is contracting away vertices of degree 1 and 2.
Automorphism groups
There’s a question of how combining or modifying groups affects their automorphism groups. There is, unfortuntely, often a lot of caveats to these results, because of questions of how components mix or new “unexpected” symmetries can appear.
The only thing I’ll say here for now, because it’s strange and easily forgotten, is that corona products were initially defined in order to give a graph description of wreath products. As Frucht and Harary prove, the automorphism map Γ
carries the corona product G1○G2
to the group wreath product – so, Γ(G1○G2) = Γ(G1) wr Γ(G2)
– if and only if: either G1
has no isolated points or Comp(G2)
has no isolated points (or both).
Sabidussi proved a similar result that the lexicographic product also “usually” makes a wreath product, under a more complicated condition: if and only if (G1 has no false twins^{12} or G2 is connected) and (G1 has no true twins or Comp(G2)
is connected).
Disjoint union “usually” becomes a direct product of automorphism groups. There are extra symmetries if there are isomorphic connected components in the original graphs. Graph join also “usually” works, a double graph “usually” gives you Γ(G) wr Z2
… a bipartite double graph “usually” gives you a semidirect(?) product Γ(G1) x Z2
, unless G was bipartite to start with, then you get something more like Γ(G) wr Z2
… and so on.
Footnotes
I have a todo list for this page.

Also called the categorical product, because it forms the natural product in the category of graphs under graph homomorphisms. ↩

Tensor products can be described to have an identity in the form of a single selfloop, the bouqet
B1
. This also works for modular products, if the definition is modified appropriately to handle selfloops a particular way. ↩ ↩^{2} 
Also called the composition of graphs. ↩

K1
is a twosided inverse for this noncommutative operation. ↩ 
Homomorphic products have the onevertex zeroedge graph as an identity, but only when on the right side of the operation. On the left side, you could modify the definition to handle selfloops such that
B1
is an identity, but this would be extremely unnatural (while staying compatible with the definition on simple graphs). ↩ 
Corona products have no identity on the left (not even with selfloop tricks), but
K0
is an identity on the right. ↩ 
Also known as graph sum. ↩

The bipartite double cover is equivalently a tensor product with K2. ↩

Dissolution is also called Smoothing. “Dissolution” is unfortunately both the name of the operation (on one vertex) and a relationship between graphs G and H, if H is formed from G by repeated dissolution. ↩

Subdivision is also called Expansion ↩

Lifting targets a
P_3
, or path graph on 3vertices: two edges (u,v) and (v,w) that share a common endpoint. ↩ 
Vertices are false twins if they have the same open neighborhood (their neighbors, but not including themselves). They are true twins if they have the same closed neighborhod (their neighbors, plus themselves). ↩ ↩^{2}

When we say that K_{n} is a “counterexample” to an ordering property, we mean that the property implies something about a set that fails. For instance, the Well Quasi Ordering condition, WQO, states that there should be no infinite antichains, no infinite set of graphs that all fails to be ordered by the relationship. K_{n} shows that graph isomorphism is not WQO, because it forms an infinite set of graphs that are all nonisomorphic. The cycle graphs C_{n} show that subgraph and induced subgraph are not WQO, because none of the cycle graphs have each other as subgraphs. ↩

P
is polynomial time to recognize if G contains H.NPC
means it is NPcomplete. For insta ↩ 
ParaNPC means that deciding a fixed parameter (e.g. k=3 – is the graph 3colorable?) is already NPComplete, this gives the parameterized class paraNPcomplete, or paraNPC. ↩

Cliques are a “classic” example of (induced) subgraph recognition being NPcomplete, because MAXCLIQUE is an NPcomplete problem. For another example, cycles are an example of why “spanning subgraph” is hard to check, because a cycle that is a spanning subgraph of G is a Hamiltonian cycle, and Hamiltonian cycle checking is NPcomplete. ↩

We could say, H is an induced subgraph of G iff there is an injective homomorphism that preserves adjacency and nonadjacency. From the perspective of a graph as a relational structure (with the only relation between adjacency), “induced subgraph” is then the same as the notion of embedding used in universal algebra and logic. So, occasionally the relationship of graphs is referred to as “embedding”, or the mapping as “the embedding”. But this should not be confused with the notion of Graph embedding, which studies ways to put graphs on surfaces of different genera, or crossing numbers and the like. ↩

While H is a dissolution of G if G can be reduced to H by repeatedly dissolving degree2 vertices, the dual relationship is that G is a subdivision of H, by repeatedly subdividing the edges of H. ↩

NPHardness was originally “observed” in On the complexity of finding isoand other morphisms for partial ktrees by J. Matoušek, R. Thomas, although the reduction is somewhat nontrivial and doesn’t seem to be written down anywhere. ↩

There is a simple FPT algorithm for dissolution checking. We’ll say that a vertex is a branchpoint if it has degree 3 or more. Dissolution preserves the number of branchpoints in a graph, so first check that G and H have the same number of branchpoints. There are at most $k=V(H)$ many branchpoints in H, and so at most $k$ many branchpoints in G as well. Then just check each of the $k!$ different ways to map the branchpoints of H to those of G. A map is a valid solution if the paths a given pair of branchpoints in G are longer than the paths between the corresponding branchpoints in H. So each map can be checked in $O(n)$ time, and the dissolution can be checked in $O(k^k n)$ time. For homeomorphism checking, the same algorithm can be used, where all applicable dissolutions are first applied. ↩ ↩^{2}

To test the homeomorphism of two graphs, first apply all possible dissolutions, so that there are no degree2 vertices. What is left is a graph isomorphism problem, so this is in the complexity class GI. On the other hand, any GI problem can be turned into a homeomorphism problem by appropriately “decorating” all the degree2 vertices so that they are no longer degree2, with a unqiue decoration so that they cannot be confused for anything other than what was once a degree2 vertex. For instance, decorating each vertex with $V(G)+1$ many degree1 neighbors is enough. ↩

Topological minor is also known as Topological subgraph, Homeomorphic subgraph (see Kuratowksi’s theorem), or even Subgraph homeomorphism. ↩

Graphs that are induced topological minors must also be topological minors, and induced minors. Since neither of those are wellquasiordered (see the table for references), induced topological minors can’t be WQO either. ↩

Immersion minor is also known as just Immersion. Some authors, e.g. this distinguish that H is the immersion minor of G, and the mapping $f$ is the immersion itself. ↩

The fact that $H=C_n$ is enough to show that induced immersion is NPcomplete is mentioned in Belmonte et al., in Lemma 1. The proof is ommitted there, sadly, and I cannot find it online. (I haven’t really tried to reproduce it.) ↩

The difference between an ordinary homomorphism, faithful homomorphism, and full homomorphism is as follows. All of them agree that edges must map to edges. A full homomorphism requires that nonedges map to nonedges, or we could equivalently say that only “necessary” edges appear in the image. A faithful homomorphism says for each edge in the image, at least one edge in the preimage must map there, so it’s a weaker notion of what a “necessary” edge is. There’s more discussion here. ↩

Full homomorphism is also known as Strong homomorphism, especially from the perspective of universal algebra and mathematical logic. ↩

Epimorphism is also known as Surjective homomorphism. ↩

Monomorphism is also known as Injective homomorphism. ↩