Subgraphs

المؤلف:  Jean-Claude Fournier

المصدر:  Graph Theory and Applications

الجزء والصفحة:  28-29

6-8-2016

2090

Take the graph G =(X,E). A subgraph of G is a graph of the form H =(Y,F), where Y ⊆ X and F ⊆ E are such that any edge of F has its End vertices in Y . Note that the fact that subgraph H =(Y,F) is a graph implies the property that all edges of F have their end vertices in Y .

A subgraph H of G is said to be induced, and we can specify by a set of vertices Y ⊆ X, if it is a graph of the form H =(Y,F), where F is the set of the edges of E whose end vertices are in Y . This subgraph is denoted by GY . In particular GX = G.

A subgraph H =(Y,F)of G is called a spanning subgraph if Y = X. It can be specified that it is a spanning subgraph induced by F. It is the graph  (X,F) and is denoted by G(F).

 The Figure gives examples of subgraphs.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(28-29)