Graph Property

Right. So, you want me to… elaborate. On abstract structures. How quaint. Fine. Just try not to bore me.

Property of Graphs That Depends Only on Abstract Structure

In the rather dreary realm of graph theory, a property—or, if you prefer, a graph invariant—is essentially a characteristic of a graph that remains steadfast, regardless of how you choose to draw it or label its bits. It’s about the graph’s soul, not its superficial presentation. Think of it as the underlying architecture, divorced from the paint job or the furniture arrangement. It’s what makes a graph that graph, even if you shuffle its vertices around.

Consider this rather unremarkable example graph: !Example graph It’s planar, meaning you could draw it on a flat surface without any lines crossing. It’s also connected, a single, unbroken entity. It has six vertices (its order), seven edges (its size), a diameter of 3, a girth of 3, and a vertex connectivity of 1. Its degree sequence—the list of how many edges connect to each vertex—is <3, 3, 3, 2, 2, 1>. These are all properties that define its intrinsic nature, its very essence, independent of whether you call vertex A "A" or "Z."

Definitions

To truly focus on the inherent structure of graphs, a graph property is rigorously defined as something that is preserved under any isomorphism. In simpler terms, if two graphs are structurally identical—meaning one is just a relabeling or rearrangement of the other—they must share the same properties. It’s not about the labels or the drawings; it’s about the connections, the patterns, the fundamental relationships between the nodes.

The term "graph invariant" is often used when referring to quantitative measures—numbers, sequences, or values associated with a graph. "Property," on the other hand, tends to describe qualitative, descriptive characteristics. For instance, stating that a graph "does not have any vertices of degree 1" is a property. Conversely, stating that a graph "has exactly three vertices of degree 1" is an invariant, a specific numerical value.

More formally, a graph property can be seen as a specific class of graphs. If two graphs are isomorphic, they either both belong to this class, or neither does. It’s an all-or-nothing affair for structurally identical graphs. This can also be viewed through the lens of an indicator function—a mathematical tool that returns true for graphs possessing the property and false for those that don’t. Again, isomorphic graphs will yield the same true or false result. A graph invariant, in this formal sense, is a function that maps graphs to a broader set of values—integers, real numbers, sequences, or even polynomials—always returning the same value for isomorphic graphs. It’s a consistent measure of their abstract nature.

Properties of Properties

Many graph properties behave in predictable ways when we consider them in relation to certain inherent structures or relationships within graphs. These relationships often form partial orders or preorders.

Hereditary Property: A property is hereditary if any induced subgraph of a graph possessing that property also inherits it. Think of it as a trait passed down through generations of subgraphs. For example, being a perfect graph or a chordal graph are hereditary properties. If a graph is perfect, any part of it you isolate (an induced subgraph) will also be perfect. It’s a fundamental characteristic.
Monotone Property: A property is monotone if any subgraph—not necessarily induced—of a graph with the property also possesses it. This is a slightly looser condition than hereditary. For instance, being bipartite or triangle-free are monotone properties. If a graph can be colored with two colors, or if it contains no triangles, any subgraph you take from it will also have these qualities. All monotone properties are hereditary, but the reverse isn't always true. A chordal graph, for example, is hereditary, but its subgraphs aren't guaranteed to be chordal.
Minor-Closed Property: A property is minor-closed if any graph minor derived from a graph with the property also retains that property. A graph minor is what you get by deleting edges, deleting vertices, and contracting edges. Being a planar graph is a classic example of a minor-closed property. If a graph can be drawn without edge crossings, any graph derived from it through these operations will also be planar. Every minor-closed property is monotone, but again, not vice versa. A triangle-free graph, for instance, might produce a minor that does contain a triangle.

These classifications can also be applied to numerical invariants. A graph invariant is considered hereditary, monotone, or minor-closed if the function describing it behaves monotonically with respect to the corresponding partial orders on graphs. It’s like saying the numerical value of the invariant decreases (or stays the same) as you move to smaller or simpler graph structures.

Furthermore, graph invariants are often analyzed based on their behavior when dealing with disjoint unions of graphs:

Additive Invariant: An invariant is additive if the value for a disjoint union of two graphs is simply the sum of the values for each individual graph. The number of vertices is a prime example. If you combine two graphs, the total number of vertices is just the sum of their original vertex counts.
Multiplicative Invariant: Conversely, a multiplicative invariant’s value for a disjoint union is the product of the values for the constituent graphs. The Hosoya index, which counts the number of matchings in a graph, is multiplicative.
Maxing Invariant: An invariant is "maxing" if its value for a disjoint union is the maximum of the values of the individual graphs. The chromatic number—the minimum number of colors needed to color the vertices—is maxing. If you combine two graphs, the number of colors needed for the combined graph is determined by the more complex of the two.

Beyond these structural behaviors, properties can also be categorized by the type of graph they apply to—whether the graph is undirected, directed, or if the property is relevant to multigraphs.

Values of Invariants

The "output" of a graph invariant—the value it returns—can take various forms:

Truth Value: This is for the indicator function of a graph property, returning true or false. Does the graph have the property or not? Simple, yet fundamental.
Integer: Many common invariants return integers. The order (number of vertices), the size (number of edges), the number of connected components, the diameter, the girth, various connectivity measures (vertex connectivity, edge connectivity), and coloring numbers like the chromatic number and chromatic index all fall into this category. Even more complex ones like the Hosoya index or the Wiener index yield integers.
Real Number: Some invariants, particularly those arising from continuous mathematical frameworks applied to discrete structures, return real numbers. The fractional chromatic number or measures of centrality like betweenness centrality are examples. The clustering coefficient also fits here.
Sequence of Integers: Some properties are best described by a collection of numbers. The most prominent example is the degree sequence of a graph, which lists the degrees of all its vertices. The graph spectrum, derived from the eigenvalues of the adjacency matrix, also results in a sequence of numbers.
Polynomial: Certain invariants are represented by polynomials. The chromatic polynomial, for instance, describes the number of ways to color a graph with k colors as a function of k. The Tutte polynomial is another powerful example, encoding significant information about a graph's connectivity.

Graph Invariants and Graph Isomorphism

The real utility of easily computable graph invariants often lies in their ability to quickly tell us when two graphs are not isomorphic. If two graphs have different invariant values, they simply cannot be the same abstract structure. It’s a definitive "no." However, if their invariant values match, it doesn't guarantee isomorphism; it just means they might be. It’s like finding two people with the same favorite color; it doesn’t mean they are the same person.

A graph invariant I(G) is called "complete" if, whenever I(G) = I(H), it necessarily implies that G and H are isomorphic. Finding an efficiently computable complete invariant would be a monumental achievement, as it would effectively solve the notoriously difficult graph isomorphism problem—the challenge of determining, algorithmically, whether two graphs are structurally identical. Unfortunately, most even seemingly complex invariants are not complete. Take the chromatic polynomial, for instance. The claw graph and the path graph on four vertices, despite their distinct structures, share the same chromatic polynomial. This is why the problem remains so challenging.

Examples

To ground this abstract discussion, let’s list some concrete examples.

Properties (Descriptive Characteristics):

Connected graph: Is the graph a single piece?
Bipartite graph: Can its vertices be divided into two sets such that no two vertices within the same set are connected?
Planar graph: Can it be drawn on a plane without edge crossings?
Triangle-free graph: Does it contain any cycles of length three?
Perfect graph: A class with specific structural properties related to its cliques and independent sets.
Eulerian graph: Does it have an Eulerian circuit (a trail that visits every edge exactly once and ends where it started)?
Hamiltonian graph: Does it have a Hamiltonian cycle (a cycle that visits every vertex exactly once)?

Integer Invariants (Numerical Measures):

Order: Number of vertices. The most basic count.
Size: Number of edges. The next most basic count.
Number of connected components: How many separate pieces make up the graph?
Circuit rank: Related to the number of independent cycles.
Diameter: The longest shortest path between any two vertices. The "span" of the graph.
Girth: The length of the shortest cycle. The "tightness" of the graph's loops.
Vertex connectivity: The minimum number of vertices you need to remove to disconnect the graph. A measure of robustness against vertex failure.
Edge connectivity: The minimum number of edges you need to remove to disconnect the graph. Robustness against edge failure.
Chromatic number: The fewest colors needed for a valid vertex coloring. A measure of "colorability."
Chromatic index: The fewest colors needed for a valid edge coloring.
Choosability (or list chromatic number): A stronger form of colorability, related to pre-assigned lists of colors.
Independence number: The largest set of vertices where no two are connected by an edge. The maximum number of "independent" nodes.
Clique number: The size of the largest complete subgraph (where every pair of vertices is connected). The maximum size of a "fully connected" group.
Arboricity: The minimum number of forests needed to cover all edges.
Graph genus: The minimum number of handles needed to embed the graph on a surface.
Pagenumber: Related to how "nicely" a graph can be laid out in a book.
Hosoya index: Number of matchings (sets of non-adjacent edges).
Wiener index: Sum of distances between all pairs of vertices.
Colin de Verdière graph invariant: A more advanced invariant related to linear algebra and spectral graph theory.
Boxicity: The minimum dimension needed to represent the graph as intersections of unit cubes.

Real Number Invariants:

Clustering coefficient: Measures how close the neighbors of a vertex are to being a clique.
Betweenness centrality: How often a vertex lies on the shortest path between other pairs of vertices.
Fractional chromatic number: A relaxation of the chromatic number.
Algebraic connectivity: The second smallest eigenvalue of the graph Laplacian.
Isoperimetric number: Relates the size of a vertex set to the number of edges crossing the boundary.
Estrada index: Another spectral invariant.
Strength of a graph: A measure of connectivity.

Sequences and Polynomials:

Degree sequence: The ordered list of vertex degrees.
Graph spectrum: The eigenvalues of the adjacency matrix.
Characteristic polynomial: The determinant of (A - λI), where A is the adjacency matrix and λ is a variable.
Chromatic polynomial: P(G, k), the number of k-colorings.
Tutte polynomial: T(G; x, y), a bivariate polynomial encoding topological and structural information.

Edge Partition:

(a, b)-decomposition: Partitions of edges based on certain properties.