Varieties of graphs and graph’s models

 

Due to the vast breadth of the usefulness of graphs, the terminology varies widely, not only from one graph variety to another, but also from one application to another. The table in Fact 1 gives synonyms for several terms.

Definitions:

A vertex is usually conceptualized as a point. Abstractly, it is a member of the first of two sets that form a graph.

An edge is usually conceptualized as a line, either joining one vertex to another or joining a vertex to itself. Abstractly, it is a member of the second of two sets that form a graph.

A proper edge (or link) is an edge that joins one vertex to another.

A loop (or self-loop) is an edge joining a vertex to itself.

The endpoints of an edge are the vertices that it joins. A loop has only one endpoint.

An incidence rule specifies the endpoints of every edge.

An edge e is incident with a vertex v if v is an endpoint of e.

A graph is a set V of vertices and a set E of edges (both sets finite unless declared otherwise) such that all the endpoints of edges in E are contained in V . It is often denoted G = (V,E), or (VG,EG),or (V (G),E(G)). Sometimes, each edge is regarded as a pair of vertices.

An isolated point of a graph G = (V,E) is a vertex in V that is not the endpoint of any edge in E.

Vertices u and v are adjacent if there is an edge whose endpoints are u and v.

Two edges are adjacent if they have a common endpoint.

A neighbor of a vertex is any vertex to which it is adjacent.

An attribute of the edge-set or vertex-set is a feature such as length, cost, or color sometimes attached to graphs.

A graph model is a graph which (quite frequently, in applications) may have additional attributes on its edges and/or vertices. The vertices and edges of the model may represent arbitrary objects and relationships from the context of the application.

A weighted graph is a graph model in which each edge is assigned a number called the weight or the cost.

A node is sometimes a synonym for a vertex and sometimes refers to whatever is modeled by a vertex in a graph model.

A line is sometimes a synonym for an edge and sometimes refers to whatever is modelled by an edge in a graph model.

A multi-edge in an undirected graph is a set of more than one edge with the same endpoints, and in a digraph a set of more than one edge such that each edge in the set has the same head and each edge in the set has the same tail. A graph with a multi-edge is also said to have multiple edges or parallel edges.

A multi-edge of multiplicity n is a set of n edges with the same endpoints.

A set of parallel edges is a set of edges with the same endpoints, i.e., a multi-edge. A pair of anti-parallel arcs is a pair of oppositely directed arcs between the same two endpoints.

A graph is simple if it has no loops or multi-edges. Topologists often say simplicial, because such a graph is a special case of a “simplicial complex”.

A multi-graph is another name for a graph with multi-edges but no self-loops, used for emphasis when the context is largely restricted to simple graphs.

A pseudo-graph (or general graph) is another name for a graph in which loops and multi-edges are permitted, used for emphasis when the context is largely restricted to loopless graphs.

A direction on an edge is an ordering for its endpoints so that the edge goes from one endpoint and to the other. Any edge, including a self-loop, can be directed by giving it a sense of forward progression, e.g., in a graph drawing, by placing an arrowhead to show which way is forward, or by ordering the endpoints.

An arc is another name for a directed edge.

The tail of an arc is the vertex at which the arc originates.

The head of an arc is the vertex at which the arc terminates.

A directed graph or digraph is a graph in which every edge is directed.

A strict digraph has no self-loops and no pair of arcs with the same tail and head.

The degree of vertex v, deg(v),is the number of proper edges plus twice the number of loops incident with v. Thus, in a drawing, it is the number of edge-endings at v.

The valence of a vertex is a synonym for degree adapted from terminology in chemistry.

The degree sequence of a graph is the sequence of the degrees of its vertices, most often sorted into size order, ascending or descending.

A regular graph is a graph such that all vertices have the same degree. It is called
k-regular if the vertices all have degree
k.

A graphical sequence is a sequence of nonnegative integers that is the degree sequence of some simple graph.

The number of vertices of a graph is sometimes called the order.

The number of edges of a graph is sometimes called the size.

The empty graph is the graph whose vertex set and edge set are both empty. This is

also called the null graph (and is sometimes not considered to be a graph).

The trivial graph is the graph with one vertex and no edges.

Facts:

1. The following table gives lists of some synonymous graph theory terms:

vertex: point, node

edge: line

loop: self-loop

neighbor: adjacent vertex

arc: directed edge

degree: valence

number of vertices: order

number of edges: size

nonsimple graph: pseudograph, general graph

loopless nonsimple graph: multi-graph

empty graph: null graph

2. The following table lists the varieties of graphs:

graph variety        loops allowed?      multi-edges allowed?

digraph                         YES                            YES

general graph               YES                             YES

multi-graph                   NO                              YES

pseudo-graph                YES                            YES

simple graph                  NO                              NO

strict digraph                  NO                             NO*

*at most one arc in each direction between two vertices.

3. In a drawing of a graph, the degree of a vertex v equals the number of edge-ends at v.

The degree of v need not equal the number of edges at v, since each loop contributes both its ends toward the degree.

4. Euler’s theorem: In every graph, the sum of the degrees equals twice the number  of edges. From this result it follows that in all graphs the sum of the degrees of all vertices is even.

5. In every graph the number of vertices of odd degree is even.

6. The name handshaking lemma is commonly applied to various elementary results about the degrees of simple graphs, especially Facts 4 and 5.

7. In every simple graph with at least two vertices, there is a pair of vertices with the same degree.

8. Havel’s theorem: A sequence is a graphical sequence if and only if the sequence obtained by deleting the largest entry d and subtracting 1 from each of the d next largest entries is graphical. (V. Havel,1955). This operation on a sequence is called Havel’s reduction.

9. A nonincreasing sequence of nonnegative integers d1, d2, . . . , dn is graphical if and only if its sum is even, and for k = 1, 2, . . . , n,

.

(P. Erd˝os and T. Gallai,1960)

10. In a computer, a graph is commonly represented as a structure with variable value. The empty graph is often used as the initial value of a graph variable, analogous to the way in which zero is used as the initial value of a numeric variable.

Examples:

1. The following figure gives examples of the various varieties of graphs. (See the table of Fact 2.)

 

 

2. Computer programming flowchart (always a digraph): Each vertex represents some programmed operation or decision, and each arc represents the flow of control to the next operation or decision.

 

 

3. Model for social networks (usually undirected): Each vertex represents a person in the network, and each edge represents a form of interaction between the persons represented by its endpoints. This is illustrated by the following graph.

 

 

4. Model for road networks (most edges undirected): Each vertex represents either an intersection of two roads or the end of a dead-end street. The absence of an endpoint in the illustration indicates that the road continues beyond what is shown. Direction on an edge may be used to indicate a one-way road. Undirected edges are two-way roads.

 

 

5. In the following graph with vertex set V = { v1, v2, v3, v4, v5 } and edge set
E = { e1, e2, e3, e4, e5, e6, e7 }, the vertex v5 is an isolated point, and the degree sequence  is (0,3,3,4,4). The edge e7 is a loop, and the three edges e4, e5, and e6 form a multi-edge.

 

 

6. Deleting the isolated vertex and the self-loop in Example 5 and then reducing the multi-edge to a single edge yields the following simple graph, whose degree sequence is (1,2,2,3).

 

 

7. The sequence (1,2,2,3,4,5) is not graphical, by Euler’s theorem (Fact 4), because its sum is odd.