Subgraphs, Paths, and Connected Graphs
Subgraph: Let H be a graph with vertex set V(H) and edge set E(H), and similarly let G be a graph with vertex set V(G) and edge set E(G). Then, we say that H is a subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G). In such a case, we also say that G is a superg
- PDF / 437,550 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 68 Downloads / 199 Views
Subgraphs, Paths, and Connected Graphs
2.1 Subgraphs and Spanning Subgraphs (Supergraphs) Subgraph: Let H be a graph with vertex set V(H) and edge set E(H), and similarly let G be a graph with vertex set V(G) and edge set E(G). Then, we say that H is a subgraph of G if V(H) ( V(G) and E(H) ( E(G). In such a case, we also say that G is a supergraph of H.
Fig. 2.1 G1 is a subgraph of G2 and G3
In Fig. 2.1, G1 is a subgraph of both G2 and G3 but G3 is not a subgraph of G2 . Any graph isomorphic to a subgraph of G is also referred to as a subgraph of G. If H is a subgraph of G then we write H ( G. When H ( G but H = G, i.e., V(H) = V(G) or E(H) = E(G), then H is called a proper subgraph of G. Spanning subgraph (or Spanning supergraph): A spanning subgraph (or spanning supergraph) of G is a subgraph (or supergraph) H with V(H) = V(G), i.e. H and G have exactly the same vertex set. It follows easily from the definitions that any simple graph on n vertices is a subgraph of the complete graph Kn . In Fig. 2.1, G1 is a proper spanning subgraph of G3 . S. Saha Ray, Graph Theory with Algorithms and its Applications, DOI: 10.1007/978-81-322-0750-4_2, Ó Springer India 2013
11
12
2 Subgraphs, Paths and Connected Graphs
2.2 Operations on Graphs The union of two graphs G1 ¼ ðV1 ; E1 Þ and G2 ¼ ðV2 ; E2 Þ is another graph G3 ¼ ðV3 ; E3 Þ denoted by G3 ¼ G1 [ G2 , where vertex set V3 ¼ V1 [ V2 and the edge set E3 ¼ E1 [ E2 : The intersection of two graphs G1 and G2 denoted by G1 \ G2 is a graph G4 consisting only of those vertices and edges that are in both G1 and G2 . The ring sum of two graphs G1 and G2 , denoted by G1 G2 ; is a graph consisting of the vertex set V1 [ V2 and of edges that are either in G1 or G2 ; but not in both. Figure 2.2 shows union, intersection, and ring sum on two graphs G1 and G2 :
Fig. 2.2 Union, intersection, and ring sum of two graphs
Three operations are commutative, i.e., G1 [ G2 ¼ G2 [ G1 ;
G1 \ G2 ¼ G2 \ G1 ;
G1 G2 ¼ G2 G1
If G1 and G2 are edge disjoint, then G1 \ G2 is a null graph, and G1 G2 ¼ G1 [ G2 : If G1 and G2 are vertex disjoint, then G1 \ G2 is empty. For any graph G, G \ G ¼ G [ G ¼ G and G G = a null graph. If g is a subgraph of G, i.e., g ( G, then G g = G - g, and is called a complement of g in G.
2.2 Operations on Graphs
13
Fig. 2.3 Vertex deletion and edge deletion from a graph G
Decomposition: A graph G is said to be decomposed into two subgraphs G1 and G2 , if G1 [ G2 ¼ G and G1 \ G2 is a null graph. Deletion: If vi is a vertex in graph G, then G vi denotes a subgraph of G obtained by deleting vi from G. Deletion of a vertex always implies the deletion of all edges incident on that vertex. If ej is an edge in G, then G ej is a subgraph of G obtained by deleting ej from G. Deletion of an edge does not imply deletion of its end vertices. Therefore, G ej ¼ G ej (Fig. 2.3). Fusion: A pair of vertices a, b in a graph G are said to be fused if the two vertices are replaced by a single new vertex such that every edge, that was incident on either a or b
Data Loading...
