Graph Operations

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`	`V1E2 + V2E1`	✅	✅	`K1`
Tensor Product¹	`G1⨯G2`	`V1*V2`	`2E1E2`	✅	✅	`B1`²
Strong Product	`G1⊠G2` Union of `G1□G2` and `G1⨯G2`.	`V1*V2`	`V1E2 + V2E1 + 2E1E2`	✅	✅	`K1`
Co-normal Product	No standard notation Union of `G1[G2]` and `G2[G1]`	`V1*V2`	`E2V1^2 + E1V2^2 - 2E1E2`	✅	✅	`K1`
Modular Product	No standard notation Union of `G1⨯G2` and `G̅1⨯G̅2`	`V1*V2`	`E1E2 + ((V1^2-V1)/2-E1)((V2^2-V2)/2-E2)`	✅	✅	`B1`²
Lexicographical Product³	`G1[G2]`	`V1 * V2`	`V1E2 + E1V2^2`	❌	✅	`K1`/`K1`⁴
Homomorphic Product	`G1⋉G2`	`V1*V2`	`V1(V2^2-V2)/2 + E1V2^2 - 2E1E2`	❌	❌	❌/`K1`⁵
Corona Product	`G1○G2`	`V1*(1+V2)`	`E1 + V1E2 + V1V2`	❌	❌	❌/`K0`⁶
Sum-like
Disjoint Union⁷	`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
Vertex addition	V+1	E
Universal neighbor addition	V+1	E+V	Add a vertex neighboring everything else.
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 double⁸	`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⁹	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.
Subdivision¹⁰	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`¹¹	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 twins¹² 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 f_V that preserve adjacency. “Induced subgraph” requires that f_V also preserves non-adjacency. 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¹³.

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¹⁴. If we hold H fixed with k many vertices, then we aim to categorize as FPT, W[1]C, XP, or paraNPC¹⁵. 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¹⁶ 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¹⁷	Vertex deletion	$u\sim v \iff f(u) \sim f(v)$ f_V injective	✅	❌ $K_n$	❌ Ref. $C_n$	❌	NPC $K_n$, Max-clique	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$, Max-clique	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¹⁸	Dissolution	$f_V$ injective $f_E$ takes edges in H to degree-2 paths in G $f_E$ bijective	✅	❌ $K_n$	❌ $K_n$	❌	NPC ¹⁹	FPT²⁰
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$	✅	GIC²¹	FPT²⁰
Minor	Vertex deletion Edge deleition Contraction	f	✅	❌ $K_n$	✅	❌	NPC $C_n$, Hamiltonian cycle	FPT
Topological Minor²²	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$	❌²³	❌	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²⁴	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$²⁵	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 self-loop deletion!)	$u\sim v \implies f(u) \sim f(v)$ f_V 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)$²⁶ f_V may be many-to-one	d	a	w	❌	c	p
Full Homomorphism²⁷	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 many-to-one	d	a	w	❌	c	p
Epimorphism²⁸	Vertex identification Edge addition Multiedge simplification (No self-loop deletion!)	f	d	a	w	❌	c	p
Monomorphism²⁹	Vertex addition Edge addition 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 twins¹² 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 self-loop, the bouqet B1. This also works for modular products, if the definition is modified appropriately to handle self-loops a particular way. ↩ ↩²
Also called the composition of graphs. ↩
K1 is a two-sided inverse for this non-commutative operation. ↩
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). ↩
Corona products have no identity on the left (not even with self-loop 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 3-vertices: 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). ↩ ↩²
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 NP-complete. For insta ↩
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. ↩
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. ↩
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. ↩
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. ↩
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. ↩
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. ↩ ↩²
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. ↩
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 well-quasi-ordered (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 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.) ↩
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. ↩
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. ↩

Alex Meiburg / Timeroot

Quantum ⊕ Physics ⊗ Algorithms