Graph Invariants are properties that are preserved by the structure of the graph, and are not exclusive to a given representation of it. Common examples include planarity and cyclicity. Make sure to use this tag only if your question involves an invariant (or a proposed invariant) of graphs or of a subclass of graphs.
A graph invariant is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph.
Many graph invariants are well-behaved with respect to certain natural partial orders or preorders defined on graphs:
- A graph invariant $P$ is hereditary if every induced subgraph of a graph with invariant $P$ also has invariant $P$. For instance, being a perfect graph or being a chordal graph are hereditary properties.
- A graph property is monotone if every subgraph of a graph with invariant $P$ also has invariant $P$. For instance, being a bipartite graph or being a triangle-free graph is monotone.
A graph property is minor-closed if every graph minor of a graph with invariant $P$ also has property $P$. For instance, being a planar graph is minor-closed. Every minor-closed invariant is monotone, but not necessarily vice versa; for instance, minors of triangle-free graphs are not necessarily themselves triangle-free.
A graph invariant is additive if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the sum of the values on G and on H. For instance, the number of vertices is additive.
- A graph invariant is multiplicative if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the product of the values on G and on H. For instance, the Hosoya index (number of matchings) is multiplicative.
- A graph invariant is maxing if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the maximum of the values on G and on H. For instance, the chromatic number is maxing.
In addition, graph invariants can be classified according to the type of graph they describe: whether the graph is undirected or directed, whether the property applies to multigraphs, etc.
Source for more examples: https://en.wikipedia.org/wiki/Graph_property#Examples