Loop (graph theory) Encyclopedia: Wikipedia & Grokipedia

Loop (graph theory)

current hub

Read side by side

Loop (graph theory)

View on Wikipedia

from Wikipedia

In graph theory, a loop (also called a self-loop or a buckle) is an edge that connects a vertex to itself. A simple graph contains no loops.

Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges between the same vertices):

Where graphs are defined so as to allow loops and multiple edges, a graph without loops or multiple edges is often distinguished from other graphs by calling it a simple graph.
Where graphs are defined so as to disallow loops and multiple edges, a graph that does have loops or multiple edges is often distinguished from the graphs that satisfy these constraints by calling it a multigraph or pseudograph.

In a graph with one vertex, all edges must be loops. Such a graph is called a bouquet.

Degree

[edit]

For an undirected graph, the degree of a vertex is equal to the number of adjacent vertices.

A special case is a loop, which adds two to the degree. This can be understood by letting each connection of the loop edge count as its own adjacent vertex. In other words, a vertex with a loop "sees" itself as an adjacent vertex from both ends of the edge thus adding two, not one, to the degree.

For a directed graph, a loop adds one to the in degree and one to the out degree.

References

[edit]

Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (February 1, 1997). ISBN 0-07-005489-4.
Bollobás, Béla; Modern Graph Theory, Springer; 1st edition (August 12, 2002). ISBN 0-387-98488-7.
Diestel, Reinhard; Graph Theory, Springer; 2nd edition (February 18, 2000). ISBN 0-387-98976-5.
Gross, Jonathon L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (December 30, 1998). ISBN 0-8493-3982-0.
Gross, Jonathon L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (December 29, 2003). ISBN 1-58488-090-2.
Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (November 27, 2002). ISBN 1-58488-291-3.

External links

[edit]

This article incorporates public domain material from Paul E. Black. "Self loop". Dictionary of Algorithms and Data Structures. NIST.

Revisions and contributors Edit on Wikipedia Read on Wikipedia

Loop (graph theory)

View on Grokipedia

from Grokipedia

In graph theory, a loop, also known as a self-loop, is a degenerate edge that connects a single vertex to itself.^[1] Loops represent self-relationships or feedback within the structure of a graph and are distinct from standard edges that link distinct vertices.^[2] Loops are prohibited in simple graphs, which consist of undirected edges between distinct vertices with no multiples or self-connections, ensuring a clean representation of pairwise relationships.^[1] However, they are permitted in more general structures such as multigraphs, which allow multiple edges between vertices, and pseudographs, which explicitly include loops alongside multiples.^[1] In directed graphs, loops manifest as arcs from a vertex to itself, contributing to both in-degree and out-degree calculations.^[3] A key property of loops in undirected graphs is their contribution to vertex degree: each loop incident to a vertex adds 2 to its degree, as it is considered to have two endpoints at that vertex, preserving the handshaking lemma where the sum of degrees equals twice the number of edges.^[4] In adjacency matrix representations, a loop at vertex

v

corresponds to a non-zero entry on the diagonal at position

(v, v)

, often valued at 1 or 2 depending on the convention for multiplicity.^[5] Loops also form cycles of length 1, influencing concepts like Eulerian circuits in graphs where degree parity matters, though they are often excluded from connectivity analyses as they do not affect paths between distinct vertices.^[4]

Definition

In Undirected Graphs

In an undirected graph, a loop is a degenerate edge that connects a vertex to itself, also known as a self-loop.^[1] Formally, it is represented as an unordered pair

\{v, v\}

where

v

is the vertex, distinguishing it from regular edges that connect distinct vertices.^[1] Unlike edges between different vertices, a loop does not imply directionality and is inherently symmetric. Loops are prohibited in simple graphs, which allow neither loops nor multiple edges between the same pair of distinct vertices.^[6] In contrast, multigraphs permit multiple edges between distinct vertices (though definitions vary on whether they allow loops), while pseudographs generalize further by allowing both multiple edges and loops at the same vertex, with multiple loops counted according to their multiplicity.^[7]^[8] This classification enables the modeling of more complex structures, such as those with self-referential connections. In graph drawings, loops are typically visualized as a small circle or a curved line attached directly to the vertex, ensuring clarity without overlapping other elements.^[9] Although the foundations of graph theory trace back to Leonhard Euler's 1736 analysis of the Königsberg bridges, which considered multigraphs without loops, the systematic inclusion and treatment of loops in general undirected graphs gained prominence in Dénes König's seminal 1936 monograph Theorie der endlichen und unendlichen Graphen.

In Directed Graphs

In directed graphs, also known as digraphs, a loop is formally defined as a directed edge, or arc, that originates and terminates at the same vertex

v

, denoted as

(v, v)

.^[10] This structure extends the concept of a loop in undirected graphs by adding an explicit direction to the self-connection.^[5] Simple directed graphs, which prohibit multiple arcs between the same pair of vertices, typically forbid loops to maintain a strict orientation without self-references.^[10] In contrast, multidigraphs allow loops and permit multiplicity, meaning multiple distinct arcs from

v

v

can coexist, enabling more complex self-interactions.^[3]^[11] A loop at vertex

v

facilitates a walk of length 1 that starts and ends at

v

without departing to any other vertex, forming the simplest nontrivial closed structure in the digraph.^[11] This walk consists solely of the sequence

v, (v, v), v

, adhering to the directed traversal rules.^[12] In tournaments, defined as complete oriented graphs where every pair of distinct vertices has exactly one directed arc between them, loops are not standard and are generally excluded to preserve the pairwise competition model.^[13] However, generalizations such as tournaments with loops have been considered in certain dynamical systems contexts, allowing self-arcs to model additional vertex behaviors.^[14]

Properties

Degree Contribution

In undirected graphs, a loop at a vertex

v

is incident to

v

at both of its ends, and thus contributes 2 to the degree

\deg(v)

v

.^[15]^[16] More precisely, if

L(v)

denotes the number of loops at

v

and

e(v)

the number of edges from

v

to other vertices, then

\deg(v) = 2 \times L(v) + e(v)

.^[4]^[16] In directed graphs, a loop at a vertex

v

is an arc originating and terminating at

v

, contributing 1 to both the in-degree

\delta^-(v)

and the out-degree

\delta^+(v)

v

.^[16] Let

i(v)

be the number of incoming arcs to

v

from other vertices,

o(v)

the number of outgoing arcs from

v

to other vertices, and

L(v)

the number of loops at

v

; then

\delta^-(v) = i(v) + L(v)

and

\delta^+(v) = o(v) + L(v)

.^[16] For example, consider an undirected graph where a vertex

v

has one loop and is connected by edges to two other vertices; the degree is

\deg(v) = 2 \times 1 + 2 = 4

.^[4] This double-counting of loops in undirected graphs aligns with an extension of the handshaking lemma, where the sum of all vertex degrees equals twice the number of edges in the graph (counting loops as edges), i.e.,

\sum_{v \in V} \deg(v) = 2(|E| + |L|)

, with

|E|

the number of non-loop edges and

|L|

the total number of loops.^[15]^[16] In directed graphs, the corresponding sums satisfy

\sum_{v \in V} \delta^-(v) = \sum_{v \in V} \delta^+(v) = |A|

, where

|A|

includes loops as arcs.^[16]

Matrix Representations

In graph theory, the adjacency matrix provides a primary matrix representation for encoding loops. For an undirected graph, the presence of a loop at vertex

v

increments the corresponding diagonal entry

A_{v,v}

by 1 (or by the multiplicity in the case of multiple loops at

v

); note that some conventions use 2 instead to make row sums equal degrees. In directed graphs, the diagonal entry

A_{v,v}

similarly counts the number of self-arcs (loops) at vertex

v

, reflecting the directed nature of the edges.^[17] This can be expressed as

A_{v,v} = \text{number of loops at } v.

^[17] The incidence matrix offers another standard representation, with rows corresponding to vertices and columns to edges. In undirected graphs, a loop at vertex

v

is encoded in the column for that edge by placing two +1 entries in the row for

v

(effectively a 2 in that position to account for the loop's dual incidence), or ±1 in oriented versions where an arbitrary direction is assigned to the edge.^[18] For directed graphs, a loop at

v

contributes +1 (outgoing) and -1 (incoming) in the row for

v

, netting to 0; adjacency matrices are often preferred for simplicity in such cases.^[19] In symmetric adjacency matrices for undirected graphs, loops result in nonzero diagonal entries, which influence the matrix's eigenvalues—for instance, the trace of

A

, equal to the sum of its eigenvalues, directly gives the total number of loops across all vertices (in the convention where each loop contributes 1). Matrix methods for incorporating loops in graph representations, including adjacency and incidence forms, were advanced by Frank Harary in the 1950s as part of the development of algebraic graph theory.^[20]

Examples and Applications

Basic Examples

The simplest graph containing a loop consists of a single vertex

a

with one loop attached to it, formally defined as the undirected multigraph

G = (V, E)

where

V = \{a\}

and

E = \{(a, a)\}

. This is the smallest non-simple graph with a loop, having exactly one edge, and the degree of vertex

a

is 2, as each loop contributes 2 to the degree of its incident vertex in undirected graphs.^[21] This structure illustrates the basic presence of a self-edge without additional vertices. A more complex example involves multiple loops at one vertex alongside a standard edge. Consider an undirected multigraph with vertices

u

and

v

, where

v

has two loops and there is one undirected edge connecting

u

v

; the edge set is thus

E = \{(v, v)_1, (v, v)_2, \{u, v\}\}

. This graph has a total of 3 edges, the degree of

v

is 5 (2 from each of the two loops, plus 1 from the edge to

u

), and the degree of

u

is 1.^[21]^[22] Such a configuration, akin to a bouquet graph extended by an external edge, demonstrates how loops accumulate to increase degree disproportionately at a single vertex. In directed graphs, loops affect in-degrees and out-degrees separately. For instance, consider a directed multigraph with vertices

u

and

v

, featuring a loop at

v

(an arc from

v

v

) and a directed arc from

u

v

; the arc set is

A = \{(v, v), (u, v)\}

. Here, the in-degree of

v

is 2 (1 from the loop and 1 from the incoming arc from

u

), while the out-degree of

v

is 1 (from the loop); the out-degree of

u

is 1 and its in-degree is 0.^[21] This example highlights the loop's dual contribution to a vertex's in- and out-degrees in digraphs.

Theoretical and Practical Uses

In graph theory, loops play a significant role in theoretical analyses, particularly in spectral properties. The presence of loops modifies the adjacency matrix by introducing non-zero diagonal entries, which in turn affects the eigenvalues and the overall spectrum of the graph. For instance, the trace of the adjacency matrix equals the number of loops, influencing the sum of the eigenvalues and providing insights into the graph's structural complexity. Similarly, loops impact the Laplacian spectrum, altering energy measures and enabling the study of non-simple graphs in spectral graph theory.^[23]^[24]^[25] Regarding planarity, loops do not inherently prevent a graph from being planar, as they can be embedded as small curves around a vertex without introducing crossings; however, they complicate standard embedding algorithms and criteria, often requiring special handling in multigraph contexts to ensure non-homotopic representations. In graph isomorphism, loops must be preserved under any bijection between vertex sets, meaning isomorphic graphs with loops require matching loop multiplicities at corresponding vertices; this distinguishes loopless graphs as a subclass where isomorphisms need only preserve edge connections without self-edges.^[26]^[11] Practically, loops model self-transitions in finite state machines, where a self-loop at a state indicates that certain inputs leave the system unchanged, facilitating the representation of stable or recurrent behaviors in automata. In Markov chains, self-loops correspond to the probability of remaining in the same state, essential for analyzing stationary distributions and aperiodicity in probabilistic models represented as directed graphs. Within network theory, particularly social network analysis, self-loops capture self-reinforcement or intrinsic ties, such as an individual interacting with their own content, and they influence centrality measures like eigenvector centrality by adjusting spectral computations.^[27]^[28]^[29] In software engineering, loops can appear in dependency graphs as part of circular dependencies forming cycles that indicate problematic interconnections between modules, which tools detect to prevent compilation issues. In quantum graphs, loops are integral to modeling one-dimensional singular varieties with differential operators, allowing the study of wave propagation and spectral problems in physical systems like quantum wires connected at vertices.^[30]^[31]

Knowledge Base

Talk Channels

Special Pages

Loop (graph theory)

Loop (graph theory)

Loop (graph theory)

Degree

See also

In graph theory

In topology

References

External links

Loop (graph theory)

Definition

In Undirected Graphs

In Directed Graphs

Properties

Degree Contribution

Matrix Representations

Examples and Applications

Basic Examples

Theoretical and Practical Uses

References

History

Media collections

Loop (graph theory)

Loop (graph theory)

Loop (graph theory)

Degree

See also

In graph theory

In topology

References

External links

Loop (graph theory)

Definition

In Undirected Graphs

In Directed Graphs

Properties

Degree Contribution

Matrix Representations

Examples and Applications

Basic Examples

Theoretical and Practical Uses

References