- **Preserves Adjacency **, Preserves Non-adjacency: homomorphisms that preserve these properties.
- Structure-preserving of Simple Graph: preserves both adjacency and non-adjacency, i.e.
adjacent u v <=> adjacent h(u) h(v) - Isomorphism of Simple Graph: the bijection that is structure-preserving
- Structure-preserving of Graph: preserves the number of edges between every pair of vertices.
- Isomorphism of Graph: the bijection that is structure-preserving
- Consistent: For graph G and H, a pair of bijections (vertex and edge) is consistent if for all egde in G, the isomorphism maps its endpoints.
- The Möbius Ladder: denoted MLₙ, obtained by cross-match one pair of its parallel egdes.
- Isomorphism Type: the equivalent class under graph isomorphism.
- Isomorphism of Digraph: the bijection that is structure-preserving (thus preserves direction, i.e. head and tail)
For all G, H : Graph, G ≅ H <=> the isomorpism is consistent
∀ G H : Graph → G ≅ H → they have the same number of vertices and edges
The graph isomorphism preserves vertices degrees
The graph isomorphism preserves degree sequence
The graph isomorphism preserves degree of endpoints of edges
- Automorphism: an siomorphism to itself.
- Vertex-transitive: for all pair of vertices, there exists an automorphism that maps one to the other.
- Edge-transitive: for all pair of edges, there exists an automorphism that maps one to the other.
- Vertex Orbits: the equivalence classes of vertices of a graph under the action of the automorphism.
- Edge Orbits: the equivalence classes of edges of a graph under the action of the automorphism.
All vertices in the same orbit have the same degree.
All edges in the same orbit have the same pair of degrees at their endpoints.
- Subgraph, Supergraph, Subdigraph
- Proper subgraph
- Span: a subgraph is said to span a graph if they have the same vertex set.
- Spanning Tree: a spanning tree is a spanning subgraph that is a tree.
- Forest: acyclic graph
- Clique: maximal subset of mutually adjacent vertices in a graph.
- Clique Number: denoted ω(G), the number of vertices in a largest clique in G.
- Independent Set: subset of mutually non-adjacent vertices in a graph.
- Independence number: denoted α(G), the number of vertices in a largest independent set in G.
- Vertex-subset-induced Subgraph: denoted G(U), the subgraph induced on a vertex subset U of G, with all edges that have both endpoints in U.
- Egde-subset-induced Subgraph: denoted G(D), the subgraph induced on a edge subset D of G, with all vertices that are endpoints in D.
- Center: denoted Z(G), the subgraph induced on the set of central vertices of the graph G.
- Local Subgraph (or Neighborhood Subgraph) of a vertex v, denoted L(v), is the subgraph induced on the neighbors of v
A graph is connected <=> It contains a spanning tree
Every acyclic subgraph of a connected graph G is contained in at least one spanning tree of G
Graph isomorphism preserves subgraph locality
- Component: denoted c(G), maximal connected subgraphs of a graph, or alternatively, a subgraph induced by an equivalence class of the reachability relation on VG.
- Component of a vertex v: denoted C(v), the subgraph induced by the subset of all vertices reachable by v.
- Vertex-deletion Subgraph: denoted G - v, is the subgraph induced by the vertex-set VG - {v}, i.e. VG' = VG - {v}, EG' = { e in EG | v not in endpoints of e}
- Edge-deletion Subgraph: denoted G - e, is the subgraph induced by the edge-set EG - {v}, i.e. VG' = VG, EG' = EG - {e}
- Vertex-cut: a vertex subset U of a graph G such that c(G - U) > c(G)
- Cut-vertex (or Cutpoint): is a vertex-cut consisting of a single vertex.
- Edge-cut: a edge subset D of a graph G such that c(G - D) > c(G)
- Cut-edge (or Bridge): is a edge-cut consisting of a single edge.
- Cycle-edge: an edge that lies in some cycle of that graph.
- Vertex-deletion subgraph list:
[ G - v | v in VG ] - Reconstruction Deck: a vertex-deletion subgraph list without labels on the vertices, each subgraph being regarded as a card.
- Graph-reconstruction Problem: is to decide whether 2 non-isomorphic simple graph with 3 or more vertices can have the same reconstruction deck.
- Reconstruction Conjecture:
[ G - vi ≅ H - wi ] => G ≅ H - Adding an Edge, Adding an Vertex
- Primary maintenance operation: any of the above operation.
- Secondary maintenance operation: composed by Primary maintenance operations
- Union: disjoint union of the vertex-set and the egde-set of 2 graphs.
- n-fold Self-union: copies of a graph.
- Join a new vertex v to each vertex of a graph G, then the resulting graph is called the Join of v to G, or the Suspension of G from v, denoted G + v
- Wheel: denoted Wₙ, the join of K₁ + Cₙ.
- Even Wheel, Odd Wheel
- Edge Complement: make adjacent vertices non-adjacent, non-adjacent vertices adjacent.
Let e be an edge of a connected graph G. G - e is connected <=> e is a cycle-edge of G
An edge is a cut-edge <=> not a cycle edge
c(G - e) | e is a cycle-edge = c(G)
| otherwise = c(G) + 1
The number of vertices and edges can be calculated from its vertex-deletion subgraph list
| EG | = 1 / (n - 2) * sum reconstruction deck of G
The degree sequence can be calculated from its vertex-deletion subgraph list
Any regular graph can be reconstructed from its reconstruction deck.
For all H : Graph, diam(H) = d => there exists a graph G, rad(G) = d, Z(G) = H
ω(G) = α(-G) and α(G) = ω(-G)
- Graph invariant: properties preserved by graph isomorphisms.
- Image of Walk: let f : G -> H be a graph isomorphism, W be a walk in G, the image of walk of W be f(W) = <f(v0), f(e0) ... >
Graph isomorphism preserves the multiset of degrees of neighbors.
Graph isomorphism preserves edge-multiplicity
Graph isomorphism preserves walks, trails, paths and cycles, and their lengths.
Graph isomorphism preserves the number of trails, paths and cycles of the same length l for some l.
Graph isomorphism preserves the diameter, the radius, and the girth.
Graph isomorphism preserves the number of distinct subgraphs of the same isomorphism type.
G ≅ H <=> -G ≅ -H
- Adjacency Matrix of a Simple Graph: denoted AG, is the symmetric matrix whose rows and columns are both indexed by identical orderings of VG. such that:
AG[u, v] = if u and v are adjacent then 1 else 0 - Adjacency Matrix of a Simple Digraph: denoted AG, is the matrix (not symmetric) whose rows and columns are both indexed by identical orderings of VG. such that:
AG[u, v] = if there is a arc from u to v then 1 else 0 - Incidence Matrix*: is the matrix whose rows and columns are indexed by some orderings of VG and EG, such that:
IG[v, e] = o (no-no) | 1 (endpoint) | 2 (self-loop) - Incidence Matrix of Digraph: is the matrix whose rows and columns are indexed by some orderings of VG and EG, such that:
IG[v, e] = o (no-no) | 1 (head) | -1 (tail) | 2 (self-loop) - Table of Incident Edges: denoted IV:E(G), a list of vertices with all edges incident on it.
- Table of Outgoing Arcs, denoted outV:E(D), a list of vertices with edges directed from it.
- Table of Incoming Arcs, denoted inV:E(D), a list of vertices with edges directed to it.
The value of element of the nth power of a graph adjacency matrix equals the number of that walk of length r
The sum of the elements of row i of a adjacency matrix equals to the outdegree of the vertex i The sum of the elements of column i of a adjacency matrix equals to the indegree of the vertex i
The value of element of the nth power of a graph adjacency matrix equals the number of that directed walk of length r
The sum of the entries in any row of an incidence matrix is the degree of the corresponding vertex.
The sum of the entries in any column of an incidence matrix is equal to 2.
- Product:
VGxH = VG x VH,EGxG = VG x EH U EG x VH - Circlular Ladder with n Rungs: often denoted CLn,
K2 x Cn - Hypercube Graph of Dimension n (or the n-Hypercube Graph):
K2 x ... x K2 - m1 x m2 ... mn - mesh:
Pm1 x Pm2 x ... x Pmn - Wraparound m1 x m2 ... mn - mesh:
Cm1 x Cm2 x ... x Cmn - Join: denoted G + H, the graph obtained from G U H by adding en egde between each vertex of G and of H.
- n-Dimensional Octahedral Graph: deonted On,
On = if n = 0 then 2K1 else 2K + On-1 - Vertex Amalgamation, Amalgamation of G and H modulo the isomorphism f
- Subgraph of Amalgamation: the images of the original graphs.