Introduction

This short, introductory chapter contains definitions and tools necessary to follow the results presented in the forthcoming chapters. We will cover various graph notions and invariants, adjacency matrix, its eigenvalues and its characteristic polynomial, and some standard matrix theory tools that will be used later in proofs.

1.1 Graphs and Their Invariants

A simple graph is the pair G = (V,E) consisting of the vertex set V with n = | V | vertices and the edge set  ⊆(V2) with m =| E | edges. Often in the literature, n is called the order and m the size of G. Simple graphs contain neither directed nor parallel edges, so that an edge e ∈ E may be identified with the pair {u, v} of its distinct endvertices u,v ∈ V. We will write shortly uv for the set {u, v}. We will also use V(G) and E(G) to denote the vertex set and the edge set of G, if they have not been named already. To simplify notation, we will omit graph name (usually G), whenever it can be understood from the context.

For a vertex u ∈ V, the set of its neighbors in G is denoted as

u={v∈V:uv∈E}.

The degree of u is the number of its neighbors, i.e., degu = | Nu|. The maximum vertex degree Δ and the minimum vertex degree δ for G are defined as

=max?u∈Vdegu,δ=minu∈Vdegu.

Graph G is said to be d-regular graph, or just regular, if all of its vertices have degree equal to d.

A sequence :u=u0,u1,…,uk=v of vertices from V such that iui+1 ∈E, i=0,…,k−1, is called a walk between u and v in G of length k. Two vertices u,v ∈ V are connected in G if there exists a walk between them in G, and the whole graph G is connected if there exists a walk between any two of its vertices.

The distance d(u,v) between two vertices u, v of a connected graph G is the length of the shortest walk between u and v in G. The eccentricity eccu of a vertex u ∈ V is the maximum distance from u to other vertices of G,i.e.,

u=max?v∈Vd(u,v).

The diameter D and the radius r of G are then defined as

=max?u∈Veccu,r=min?u∈Veccu.

Graph =(V',E') is a subgraph of G = (V,E) if '⊆V and '⊆E. If '=V, we say that H is the spanning subgrah of G. On the other hand, if '=(V'2)∩E, i.e., if H contains all edges of G whose both endpoints are in H, we say that H is the induced subgraph of G. If U is a subset of vertices of G = (V,E), we will use G − U (or just G − u if U = {u}) to denote the subgraph of G induced by V / U. If F is a subset of edges of G, we will use G − F (or just G − e if F ={e}) to denote the subgraph (V, E / F).

A subset C ⊆ V is said to be a clique in G if uv ∈ E holds for any two distinct vertices u,v ∈ C. The clique number ω of G is the maximum cardinality of a clique in G.

A subset S ⊆ V is said to be an independent set in G if uv ∉ E holds for any two distinct vertices u,v ∈ S. The independence number α of G is the maximum cardinality of an independent set in G.

A function f: V → Z, for arbitrary set Z, is said to be a coloring of G if f(u) ≠ f(v) whenever u,v ∈ E. The chromatic number χ is the smallest cardinality of a set Z for which there exists a coloring f: V → Z. Alternatively, as −1(z),?z ?∈?Z, is necessarily an independent set, the chromatic number χ may be equivalently defined as the smallest number of parts into which V can be partitioned such that any two adjacent vertices belong to distinct parts.

A set D of vertices of a graph G is a dominating set if every vertex of V(G) / D is adjacent to a vertex of S. The domination number γ of G is the minimum cardinality of a dominating set in G.

A set M of disjoint edges of G is a matching in G. The matching number v of G is the maximum cardinality of a matching in G.

Given two graphs G = (V,E) and '=(V',E'), the function :?V→V' is an isomorphism between G and G′ if f is bijection and for each u,v ∈ Vholds {u,v} ∈ E if and only if { f(u),f(v)} ∈ E′. If there is an isomorphism between G and G′, we say that G and G′ are isomorphic and denote it as G≅G′. In case G and G′ are the one and the same graph, then we have an automorphism.

Further, a function i: G → is a graph invariant if i(G) = i(G′) holds whenever G≅G′. In other words, the value of i depends on the structure of a graph, and not on the way its vertices are labeled. All the values mentioned above

,m,Δ,Δ,D,ω,α,χ,γ,ν

are examples of graph invariants. Graph theory, actually, represents a study of graph invariants and in this book the focus will be on yet another graph invariant—the spectral radius of a graph, which is defined in the next section.

We will now define several types of graphs that will appear throughout the book. The path Pn has vertices 1,…, n and edges of the form {i, i + 1} for i = 1,…, n − 1. The cycle Cn is the graph obtained from Pn by adding edge {n,1} to it. The complete graph Kn has vertices 1,…, n and contains all edges ij for ≤i<j≤n. The complete bipartite graph n1,n2 consists of two disjoint sets of vertices V1, | V1 | = n1, and V2, | V2 | = n2, and all edges v1v2 for v1 ∈ V1 and v2 ∈ V2. The star Sn is a shortcut for the complete bipartite graph K1,n − 1. The complete multipartite graph n1,…,np consists of disjoint sets of vertices Vi, | Vi | = ni,i=1,…,p, and all edges vivj, vi ∈ Vi, vj ∈ Vj, for i ≠ j. The Turan graph n,p≅K⌈n/p⌉,…,⌈n/p⌉,⌊n/p⌋,…,⌊n/p⌋ is the (p + 1)-clique-free graph with the maximum number of edges [151]. The complete split graph CSnp = Kn− p,1,…,1 consists of an independent set of n − p vertices and a clique of p vertices, such that each vertex of the independent set is adjacent to each vertex of the clique.

The coalescence G · H of two graphs G and...