Subgraph

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

• AKA: Graph Cluster.
• Context:
  • It can range from being a Connected Subgraph to being an Unconnected Subgraph.
  • It can range from being a Subgraph Dataset to being a Formal Subgraph.
  • It can range from being a Dense Subgraph to being a Sparse Subgraph.
  • It can be found by a Subgraph Finding System (that solves a subgraph finding task).
  • It can be a Common Subgraph.
• Example(s):
  • a Clique.
  • a Subtree.
  • a Graph Edge Sequence.
  • …
• Counter-Example(s):
  • a Graph Set.
• See: Substructure, Proper Subgraph.

---

---

References

2013

• http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs
  • 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).

2009

• http://en.wiktionary.org/wiki/subgraph
  • A section of a graph or network
• http://www2.parc.com/istl/groups/hdi/sensemaking/glossary.htm
  • A connected subset of a graph. Typically, a subgraph is a connected subset of nodes and links from a larger graph. ...

---