The core routines of the GraphTheory package have been extended to support graphs with self-loops. Graphs with self-loops may be directed or undirected, and weighted or unweighted.
The number of self-loops in a graph is displayed in the graph description along with the vertex and edge count:
Several new commands have been added to work with self-loops:
|
•
|
HasSelfLoops returns true if a graph has an edge or arc to itself.
|
|
•
|
NumberOfSelfLoops returns the number of self-loops in a graph.
|
|
•
|
SelfLoops returns the set of self-loops in a graph.
|
The HasSelfLoop and NumberOfSelfLoops commands permit querying graphs for the existence and number of self-loops, respectively, while SelfLoops returns the set of vertices with self-loops.
Directed Graphs with Self-Loops
The support for self-loops extends to both directed and undirected graphs. Here is a directed graph with a self-loop at vertex 1:
The Edges command now returns self-loops in its list of edges. If only edges between distinct vertices are desired, the option selfloops=false can be specified:
The in-degree and out-degree of a vertex are each increased by one when it receives a self-loop:
Undirected Graphs with Self-Loops
We can produce a copy of G1 which discards the directionality of its edges while preserving self-loops by calling UnderlyingGraph with the selfloops option:
By convention, the degree of a vertex is increased by 2 when it receives a self-loop:
In a simple graph the smallest possible girth (length of the shortest cycle) is 3. In a graph with a self-loop, the length of the shortest cycle is 1:
By definition, any graph with a self-loop cannot be colored with any number of colors. The chromatic polynomial therefore is identically zero:
Removing self-loops
We can generate a copy of a graph with the self-loops removed simply by calling UnderlyingGraph without specifying the selfloops option:
