## Guido Caldarelli

Print publication date: 2007

Print ISBN-13: 9780199211517

Published to Oxford Scholarship Online: January 2010

DOI: 10.1093/acprof:oso/9780199211517.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 25 February 2017

# (p.256) Appendix B. Graph quantities

Source:
Scale-Free Networks
Publisher:
Oxford University Press

As already mentioned in the preface and introduction, this book is intended to be a guide in the area of networks for a large audience of readers. Our hope is that, people whose background is in economics or in biology will find this book useful. Therefore the mathematical description of graphs has been severely reduced compared with a standard text on graphs. Here we do not intend to provide all the notions of a mathematical book (partly because of the limited size of this appendix) but rather we want to give a more comprehensive description of the notions at the heart of graph theory. To make this appendix readable, we decided to write it as a self-contained structure. The price to pay is that some of the notions already presented in the text are repeated here. With all the limitations of the present space we follow here the exposition of Diestel (2005) and Bollobás (1979). These two texts should really be consulted by readers who wish to gain a more detailed knowledge of this branch of mathematics. Given this particular topic, this whole appendix must be regarded as a technical one ().

# B.1 Basics

• A graph is a way to code a relation between the elements of two sets. These two sets are called V (set of vertices) and E (set of edges). The graph indicated as G(V, E) can be drawn plotting the vertices as points and the edges as lines between them. It is not important how they are actually drawn. Ultimately the only thing that matters is to know which vertices are connected. For the moment we allow only one edge between a given pair of vertices.

• (p.257)
• A graph G(V, E) where V has n elements (n vertices) is said to have order n. Analogously, the size of a graph is the number m of its edges (the number of elements of the set E).79

• When an edge e links vertices u 1, u 2 we have that vertices u 1, u 2 are incident with the edge e. Alternatively the edge e joins v 1, u 2 that are its end vertices.

• Vertices u 1, u 2 joined by edge e are adjacent or neighbours.

• A dominating set for a graph is a set of vertices whose neighbours, along with themselves, constitute all the vertices in the graph.

• A graph defined above whose order is n cannot have more than m max edges where m max = n(n − 1)/2 (the size is smaller than m max).80 When all these possible edges are present the graph is complete and it is indicated with the symbol K n (see Fig. B.1). The opposite case happens when there are no edges at all. The graph is then empty and it is indicated by the symbol E n.

Fig. B.1 Two different examples of a complete graph. On the left K 4 and on the right K 5.

# B.2 Different kinds of graphs

## B.2.1 Weighted, directed, and oriented graphs

• Whenever a real number can be attached to an existing edge we have that the edge is characterized by a weight w. Note that in this book the weights will be almost exclusively positive real numbers, i.e. w > 0 (p.258) (see left-hand side of Fig. B.2). The graph in this case is a weighted graph, shown A directed graph G(V, E) is given by two disjoint sets E and V plus two functions I(EV) and F(EV). The first one assigns to every edge e an initial vertex I(e). The second one assigns to every edge e a final vertex F(e). More simply, every edge e has assigned a direction from one vertex I(e) to another F(e).

• Sometimes I(e) and F(e) coincide. In this case e is a loop. That is a loop is an edge between one vertex and itself. Moreover, we can have different edges directed between the same two vertices I(e) and F(e). This is the case of multiple edges.

• Whenever the direction is assigned but neither loops nor multiple edges are present, then the graph is oriented. Intuitively oriented graphs are undirected graphs where for every edge one assigns a direction.

• A multigraph is a pair of disjoint sets (V, E) together with a map EV ∪ [V]2 assigning to every edge either one or two vertices (the ends). A multigraph is then similar to a directed graph, with multiple edges and loops but no direction assigned. A sketch of the various kind of graph is presented in Fig. B.3.

• The number of edges of vertex u i in a graph is called the degree of vertex u i and is indicated here by k(u i). In the case of an oriented graph the degree can be distinguished in in-degree k in(u i) and the out-degree k out(u i). In the case of weighted graphs we will consider the weighteddegree k w(u i)of a vertex u i as the sum of the weight of the edges on u i.

• If the set V in graph G(V, E) is composed of vertices u 1, u 2, …., u n then the series k(u 1), k(u 2), …., k(u n) is a degree sequence of G(V, E). Particular importance in this book is devoted to the statistical properties of (p.259) such degree sequence. In most real networks the frequency P(k) with which a particular value k of k(u i) is present in the sequence follows a power law of the kind P(k) ∝ k γ. This case is indicated by scale-free graph.

Fig. B.2 Left: a realization of a weighted graph. The degree of vertex 4 is 6.02 (given by 0.11 + 3.21 + 1.14 + 1.56). Right: an example of an oriented graph. If the weight were the same in this case we would have an in-degree k w, in = 4.77(3.21 + 1.56) and an out-degree k w, out = 1.25(0.11 + 1.14).

Fig. B.3 The distinction between the various types of graphs.

## B.2.2 Subgraphs

• Consider two graphs G(V, E) and G′(V′E′). We can define a new graph indicated by GG′ whose vertices are in the set VV′ and the edges in the set EE′. These operations are shown in Fig. B.4. If VV′ = Φ the two graphs are disjoint. On the other hand if V′V and E;′ ⊆ E then G′(V′, E′) is an induced subgraph of G(V, E) and we indicate this by writing G′(V′, E′) ⊆ G(V, E). Finally, if G′(V′, E′) ⊆ G (V, E) and V′ = V, G′(V′, E′) is spanning of G(V, E)

• Two graphs are isomorphic if you can redraw one of them so that it looks exactly like the other.

## B.2.3 Partitions in graphs

• Let r ≥ 2 be an integer, a graph G(V, E) is called r-partite if it can be divided into r classes such that every edge has its ends in different classes. This means that vertices in the same class cannot be adjacent. If r = 2 the graph is also called bipartite

• A complete bipartite clique K i, j is a graph where every one of i nodes has an edge directed to each of the j nodes.

• (p.260)
• A bipartite core C i, j is a graph on i + j nodes that contains at least one K i, j as a subgraph.

Fig. B.4 The operations of union and intersection of two graphs.

# B.3 Paths, cycles, and trees

• A path is a non-empty graph G′(V′, E′) of the form V′ = u 0,u 1,…., u n, E′ = e 1,…. e n where u 0,u 1, ….,u n a set of vertices for which e i is an edge joining vertices u i−1 and u i. Less formally we can say that a series of consecutive edges forms a path. The number of edges in a path is called the length of the path.

• if P = e 1 + e 2 + … + e n is a path then if n ≥ 3 and we add an edge e 0 joining vertices u n and u 0, we obtain a circuit. In other words a circuit is a path whose end vertices coincide. If in the circuit all the vertices are distinct from each other the circuit is a cycle. A cycle of length k is indicated as C k. Note that a cycle is different from a loop.

• A Hamiltonian path shown in Fig. B.5 left, is a path that passes once through all the vertices (not necessarily through all the edges) in the graph. A Hamiltonian circuit is a Hamiltonian path that begins and ends in the same vertex. By construction this circuit is also a cycle.

• (p.261)
• An Eulerian path, shown in Fig. B.5 right, is a path that passes once through all the edges (not necessarily once through all the vertices) in the graph. An Eulerian circuit is an Eulerian path that begins and ends in the same edge. If the vertices in the circuit are all different then the circuit is a cycle.

• When a path exists between any couple of vertices u i, u j in a graph, the graph is connected. This property called connectivity is often misused by some authors in the sense of degree. As shown the two quantities are very different.

Fig. B.5 Left: a Hamiltonian path. Right: an Eulerian circuit.

## B.3.1 Trees

• A tree is a connected graph that does not contain cycles (also known as acyclic graph). If the graph is not connected but still acyclic then it is composed of different trees and assumes the natural name of forest.

• Vertices of degree 1 in a tree are called leaves. In any non-trivial tree there are at least two leaves.

• Sometimes it is convenient to consider one vertex of the tree as special. This vertex is called the root. A tree with a fixed root is a rooted tree.

## Notes:

(79) Since generalizations of this concept are possible and used, this class of graphs are sometimes called ‘simple graphs’.

(80) The situation is different for directed graphs or multigraphs that we define in the next section.