Sparse cuts, matching-cuts and leafy trees in graphs

In this thesis, three di®erent graph concepts are studied. A graph (V;E) consists of a set of vertices V and a set of edges E. Graphs are often used as a model for telecommunication networks, where the nodes of the network are represented by the vertices, and an edge is present between two vertices if the corresponding nodes are joined by a direct connection in the network. The two vertices joined by an edge are called its end vertices, and these two vertices are neighbors of each other. The degree of a vertex is its number of neighbors. The problems in this thesis can be explained and motivated using applications in the area of network design and analysis