*Connections* 17(1): 47-49

©1994 INSNA

**Stephen P. Borgatti
**

*Teacher's Corner** is a regular column edited
by Stephen P. Borgatti. The objective of the column is to share material helpful
to the teaching of network analysis. Contributions to the column are
appreciated. Contributions should be short (normally 2 pages or less), and
should consist of explanations of network concepts, course syllabi, synopses of
famous works, and anything else appropriate to the main objective.*

One of the mathematical underpinnings of network analysis is graph theory. In this column I present a kind of glossary of what I would consider to be a minimum working vocabulary of graph-theoretic terms and notation. The reader should be aware, however, that "...uniformity in graphical terminology will never be attained, and is not necessarily desirable." (Harary 1969, p.8).

A ** graph** (which represents an observed social relation such as
"is friends with") is denoted G(V,E) and consists of a set of

An example of a graph is given in Figure 1. It is important to note that the placing of points in the two-dimensional plane of the figure is arbitrary and conveys no information: the only meaningful property preserved by the pictorial representation is which node is linked to which other. Of course, the artist is free to locate points in accordance with some additional criteria, such as placing more central nodes towards the middle, but such a choice is no more valid than any other.

**Figure 1.** *A
graph.*

Graphs may be *directed** *or *undirected**. *A
directed graph, or *digraph**, *is one in which the lines have
direction (represented iconically with arrowheads). Directed edges are often
referred to as ** arcs**.These are used to represent potentially
non-symmetric social relations, such as "is the boss of" and
"likes". An undirected graph is one in which the lines do not have
direction. These are used to represent logically symmetric social relations,
such as "is married to" or "had sex with". Often, the term
"graph" is used in contrast to "digraph" to refer
specifically to undirected graphs. The

Graphs may be *reflexive** *or *non-reflexive**.
*In reflexive graphs, it is possible for a node to have a tie with itself,
which is called a *loop** *or, redundantly, a *self-loop**.
*In non-reflexive graphs, such links are excluded. Reflexive graphs are most
commonly used to represent networks of collectivities, such as phone calls among
cities.

Graphs may be *valued** *or *non-valued**. *A
valued graph has numbers attached to the edges, which may be used to indicate
the strength, capacity, frequency, duration or other quantitative measurement of
the link.

The *degree** *of a node is the number of nodes it is
adjacent to; or, equivalently, it is the number of edges that are incident upon
it. A node with no degree (degree 0) is an *isolate**. *A node
with degree 1 is called a ** pendant**. The graph in Figure 1 contains
two pendants and no isolates.

In a digraph, the ** indegree** of a node is the number of arcs
coming in to a node

A ** subgraph** H of a graph G is a graph whose points and lines are
also in G, so that V(H) f V(G) and E(H) f
E(G). If we select a set of nodes S from a graph G, and then select

A ** walk** is a sequence of adjacent points, together with the
lines that connect them. In other words, a walk is an alternating sequence of
points and lines, beginning and ending with a point, in which each line is
incident on the points immediately preceding and following it. The points and
lines in a walk need not be distinct. For example, in Figure 1, the sequence

A set of walks that share no points is called ** vertex-disjoint**.
A set of walks that share no edges is called

The ** length** of a walk is given by the number of lines it
contains. A

A graph is *connected** *if there exists a path from every
node to every other. A maximal connected subgraph is called a *component**.
*A *maximal subgraph* is a subgraph that satisfies some specified
property (such as being connected) and to which no node can be added without
violating the property. For example, in Figure 1, the subgraph induced by {a,b,c}
is connected, but is not a component because it is not maximal: we could add
node *d* and the subgraph induced would still be connected. The graph in
Figure 1 has just one component, which is the whole graph.

A __digraph__ that satisfies the connectedness definition given above (*i.e.*
there exists a path from every node to every other) is called *strongly
connected**. *That is, for any pair of nodes *a* and *b*,
there exists both a path from *a* to *b* and from *b* to *a*.
A digraph is ** unilaterally connected** if between every

A maximal strongly connected subgraph is a *strong component**.
*A maximal weakly connected subgraph is a *weak component**. *A
maximal unilaterally connected subgraph is a ** unilateral component**.

A *cutpoint** *is a node whose removal would disconnect the
graph. Alternatively, we could define a cutpoint as a node whose removal would
increase the number of components of the graph. In the figure, nodes *b, c,*
and *e* are cutpoints, while *a, d, *and *f* are not. A network
that contains a cutpoint will break apart if the person who occupies the
cutpoint leaves. A ** block** is a subgraph which contains no cutpoints.
A

A ** bridge** is a line whose removal disconnects the graph. An

** Menger's theorem** states that the minimum number of nodes that must be
removed to disconnect node

References

Harary, F. 1969. *Graph Theory*. Reading, MA: Addison-Wesley.