Isomorphism

An isomorphism between two graphs G and H is a bijective function f: V(G) → V(H) such that the adjacency structure of vertices and edges is preserved. In simpler terms, it means that for any vertices u and v in G, there is an edge uv in G if and only if there is an edge f(u)f(v) in H.

Two graphs \( G \) and \( H \) are identical, written \( G = H \), if \( V(G) = V(H) \), \( E(G) = E(H) \), and \( \psi_G = \psi_H \). If two graphs are identical, they can clearly be represented by identical diagrams. However, it is also possible for graphs that are not identical to have essentially the same diagram.

Automorphism

An automorphism of a graph G is a special case of isomorphism where the graph is isomorphic to itself. In other words, it is a bijective function f: V(G) → V(G) that preserves the structure of the graph. Each automorphism reflects symmetries within the graph, showcasing how the graph remains unchanged under certain vertex permutations.

Summary

Isomorphism: A bijective function preserving the adjacency structure between two graphs.
Automorphism: An isomorphism from a graph to itself, preserving the graph's structure.

Both concepts are fundamental in understanding the similarities and symmetries between different graphs. Isomorphisms help identify when two graphs are essentially the same, and automorphisms reveal symmetries within a single graph.

Labeled Graphs

In graph theory, a labeled graph is a graph where each vertex and edge has a unique label or identifier. This contrasts with unlabeled graphs, where vertices are only distinguished by their connections. The introduction of labels adds a layer of information, allowing for a more detailed representation of relationships.

The significance of labeled graphs lies in their ability to model complex systems where individual vertices and edges have specific attributes or properties. These attributes could represent anything from names, numerical values, to categorical information, depending on the context of the problem being modeled.

Formally, a labeled graph \( G \) can be defined as \( G = (V, E, \psi_V, \psi_E) \), where:

• \( V \) is the set of vertices,
• \( E \) is the set of edges,
• \( \psi_V \) is a function assigning a unique label to each vertex,
• \( \psi_E \) is a function assigning a unique label to each edge.

The labels provide a means of identification, enabling a more nuanced understanding of the graph's structure. Let's illustrate this with an example:

Example: Social Network Graph

Consider a social network graph where vertices represent individuals, and edges represent connections between them. In a labeled graph, each vertex could be labeled with the person's name, and each edge labeled with the type of relationship (e.g., friendship, professional connection).

Formally, let \( G = (V, E, \psi_V, \psi_E) \) be a labeled social network graph, where:

• \( V \) is the set of individuals with labels \( \psi_V(V) = \{ \text{Alice}, \text{Bob}, \text{Charlie}, \text{David} \} \),
• \( E \) is the set of connections with labels \( \psi_E(E) = \{ \text{Friendship}, \text{Professional} \} \),
• An edge \( (u, v) \) represents a relationship between individuals \( u \) and \( v \).

This labeled graph allows for a richer representation of the social network, capturing not only who is connected but also the nature of their connections. Analyzing such a graph becomes more insightful, especially in scenarios where the type of relationship or specific attributes of individuals matter.

Labeled graphs find applications in various fields, including computer networks, bioinformatics, and social sciences, where additional information about vertices and edges enhances the analysis and modeling capabilities.

a graph consists of vertices and edges. For a simple graph \( G = (V,E) \), where \( V \) is the set of vertices and \( E \) is the set of edges, the edge set \( E \) is typically a subset of \( \binom{V}{2} \), representing all possible 2-subsets of \( V \). In many cases, edge labels can be omitted in visual representations of such graphs. When the vertices are labelled but the edges are not, the graph is referred to as a labelled simple graph. The set of all labelled simple graphs with a vertex set \( V \) is denoted as \( G_n \), where \( n \) is the number of vertices.

A labelled simple graph \( G_n \) can be generated in \( 2^{n \choose 2} \) distinct ways. This is because, given \( n \) vertices, there are \( 2^{n \choose 2} \) possible subsets of \( \binom{V}{2} \) that represent the edges. Each subset configuration results in a unique labelled simple graph. It's important to note that this exponential growth highlights the combinatorial nature of generating labelled simple graphs.

Additionally, when we consider unlabelled simple graphs, there are \( n! \) ways to assign labels to the vertices. However, some of these assignments may result in the same labelled graph due to automorphisms, which are symmetries preserving the structure of the graph. The number of distinct labellings for a given unlabelled simple graph \( G \) on \( n \) vertices is \( \frac{n!}{\text{aut}(G)} \). Therefore, the total number of unlabelled simple graphs on \( n \) vertices is at least \( 2^{n \choose 2} n! \).

This combinatorial perspective helps understand the richness of possibilities and the inherent symmetries present in graphs, providing insights into their structural properties and potential challenges in isomorphism testing.