(p.256) Appendix B. Graph quantities
(p.256) Appendix B. Graph quantities
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 selfcontained 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}.
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 lefthand 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(E → V) and F(E → V). 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 E → V ∪ [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 indegree k ^{in}(u _{i}) and the outdegree 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 scalefree graph.
B.2.2 Subgraphs

• Consider two graphs G(V, E) and G′(V′E′). We can define a new graph indicated by G ∩ G′ whose vertices are in the set V ∩ V′ and the edges in the set E ∩ E′. These operations are shown in Fig. B.4. If V ∩V′ = Φ 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 rpartite 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.
B.3 Paths, cycles, and trees

• A path is a nonempty 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.

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 nontrivial 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.