(Redirected from subgraph)
Jump to navigation Jump to search

A Subgraph is a subset of the graph nodes and graph edges of a graph.



    • A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency relation is a subset of that of G restricted to this subset. In the other direction, a supergraph of a graph G is a graph of which G is a subgraph. We say a graph G contains another graph H if some subgraph of G is H or is isomorphic to H.

      A subgraph H is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G. We say H spans G.

      A subgraph H of a graph G is said to be induced (or full) if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has exactly the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of V(G), then H can be written as G[S] and is said to be induced by S.

      A graph that does not contain H as an induced subgraph is said to be H-free.[citation needed]

      A universal graph in a class K of graphs is a simple graph in which every element in K can be embedded as a subgraph.

      A graph G is minimal with some property P provided that G has property P and no proper subgraph of G has property P. In this definition, the term subgraph is usually understood to mean "induced subgraph." The notion of maximality is defined dually: G is maximal with P provided that P(G) and G has no proper supergraph H such that P(H).