# Graph Operations

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. Self-edges may be allowed, those are discussed in the relevant parts. A lack of labelling means that some operations (e.g. zig-zag 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 single-vertex Bouquet: a single self-loop.

Operation Notation/Description V(f(G,H)) E(f(G,H)) Com. Ass. Id
Product-like
Cartesian Product G1□G2 V1*V2 V1*E2 + V2*E1 K1
Tensor Product1 G1⨯G2 V1*V2 2*E1*E2 B12
Strong Product G1⊠G2
Union of G1□G2 and G1⨯G2.
V1*V2 V1*E2 + V2*E1 + 2*E1*E2 K1
Co-normal 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^2-V1)/2-E1)*((V2^2-V2)/2-E2) B12
Lexicographical Product3 G1[G2] V1 * V2 V1*E2 + E1*V2^2 K1/K14
Homomorphic Product G1⋉G2 V1*V2 V1*(V2^2-V2)/2 + E1*V2^2 - 2*E1*E2 ❌/K15
Corona Product G1○G2 V1*(1+V2) E1 + V1*E2 + V1*V2 ❌/K06
Sum-like
Disjoint Union7 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, series-parallel 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 Delta-Wye transformations or vertex contraction, are in the next section.

Operation V E Notes
Complement V V*(V-1)/2 - E
Line graph E ((sum of d^2)-V)/2
Mycielskian 2V+1 3E+V
Double graph 2V 4E
Bipartite double8 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
Dissolution9 Degree-2 vertex Given a degree-2 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.
Subdivision10 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_311 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-Δ Degree-3 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 twins12 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 morphism-like condition. For example, “subgraph” is defined by injective maps fV that preserve adjacency. “Induced subgraph” requires that fV also preserves non-adjacency. Where possible, this table tries to describe substructure both ways. It may be necessary that fV maps a vertex in H to a whole set of vertices in G, or vice versa, or likewise for fE.

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

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 GIC14. If we hold H fixed with k many vertices, then we aim to categorize as FPT, WC, XP, or paraNPC15. 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 difficulty16 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)$
fV bijective

$K_n$
GIC trivially FPT
Fixed vertex count
Induced Subgraph17 Vertex deletion $u\sim v \iff f(u) \sim f(v)$
fV injective

$K_n$
❌ Ref.
$C_n$
NPC
$K_n$, Max-clique
WC
$K_n$
Subgraph Vertex deletion
Edge deletion
$u\sim v \implies f(u) \sim f(v)$
fV injective

$K_n$
❌ Ref.
$C_n$
NPC
$K_n$, Max-clique
WC
$K_n$
Spanning Subgraph Edge deletion $u\sim v \implies f(u) \sim f(v)$
fV bijective

$C_n$
NPC
$C_n$, Hamiltonian cycle
trivially FPT
Fixed vertex count
Dissolution18 Dissolution $f_V$ injective
$f_E$ takes edges in H to degree-2 paths in G
$f_E$ bijective

$K_n$

$K_n$
NPC
19
FPT20
Homeomorphism Dissolution
Subdivision
$f_V$ bijects vertices of degree not 2
$f_E$ takes degree-2 paths in H to degree-2 paths in G
$f_E$ bijective

$K_n$
GIC21 FPT20
Minor Vertex deletion
Edge deleition
Contraction
f
$K_n$
NPC
$C_n$, Hamiltonian cycle
FPT
Topological Minor22 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 Minor24 Vertex deletion
Edge deletion
Lifting
$f_V$ injective
$f_E$ takes edges in H to edge-disjoint 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 edge-disjoint paths in G
$f_E$ bijective on the $E(\textrm{image of }f_V)$
d a w NPC
$C_n$25
XP

W 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
Multiedge simplification
(No self-loop deletion!)
$u\sim v \implies f(u) \sim f(v)$
fV may be many-to-one
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
fV may be many-to-one
d a w c p
Full Homomorphism27 o $u\sim v \implies f(u) \sim f(v)$
$u \not\sim y \implies f(u) \not\sim f(v)$
fV may be many-to-one
d a w c p
Epimorphism28 Vertex identification
Multiedge simplification
(No self-loop deletion!)
f d a w c p
Multiedge simplification
(No self-loop 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 co-immersion minors based on a new operation called constriction; and accordingly, restricted co-immersion 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 twins12 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

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

2. Tensor products can be described to have an identity in the form of a single self-loop, the bouqet B1. This also works for modular products, if the definition is modified appropriately to handle self-loops a particular way.  2

3. Also called the composition of graphs.

4. K1 is a two-sided inverse for this non-commutative operation.

5. Homomorphic products have the one-vertex zero-edge 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 self-loops such that B1 is an identity, but this would be extremely unnatural (while staying compatible with the definition on simple graphs).

6. Corona products have no identity on the left (not even with self-loop tricks), but K0 is an identity on the right.

7. Also known as graph sum.

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

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

10. Subdivision is also called Expansion

11. Lifting targets a P_3, or path graph on 3-vertices: two edges (u,v) and (v,w) that share a common endpoint.

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

13. When we say that Kn 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. Kn shows that graph isomorphism is not WQO, because it forms an infinite set of graphs that are all nonisomorphic. The cycle graphs Cn show that subgraph and induced subgraph are not WQO, because none of the cycle graphs have each other as subgraphs.

14. P is polynomial time to recognize if G contains H. NPC means it is NP-complete. For insta

15. ParaNPC means that deciding a fixed parameter (e.g. k=3 – is the graph 3-colorable?) is already NP-Complete, this gives the parameterized class para-NP-complete, or paraNPC.

16. Cliques are a “classic” example of (induced) subgraph recognition being NP-complete, because MAX-CLIQUE is an NP-complete 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 NP-complete.

17. We could say, H is an induced subgraph of G iff there is an injective homomorphism that preserves adjacency and non-adjacency. 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.

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

19. NP-Hardness was originally “observed” in On the complexity of finding iso-and other morphisms for partial k-trees by J. Matoušek, R. Thomas, although the reduction is somewhat nontrivial and doesn’t seem to be written down anywhere.

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

21. To test the homeomorphism of two graphs, first apply all possible dissolutions, so that there are no degree-2 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 degree-2 vertices so that they are no longer degree-2, with a unqiue decoration so that they cannot be confused for anything other than what was once a degree-2 vertex. For instance, decorating each vertex with $|V(G)|+1$ many degree-1 neighbors is enough.

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

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

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

25. The fact that $H=C_n$ is enough to show that induced immersion is NP-complete 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.)

26. 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 non-edges map to non-edges, 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

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

28. Epimorphism is also known as Surjective homomorphism

29. Monomorphism is also known as Injective homomorphism