# spanning subgraph

## spanning subgraph

[′span·iŋ ′səb‚graf]
(mathematics)
With reference to a graph G, a subgraph of G that contains all the vertices of G.
Mentioned in ?
References in periodicals archive ?
A cycle partition or cycle cover of a graph is a spanning subgraph such that each vertex is part of exactly one simple cycle.
A graph is said to be a subgraph of if and If ' contains all edges of that join two vertices in then is said to be the subgraph induced or spanned by , and is denoted by Thus, a subgraph of is an induced subgraph if If , then is said to be a spanning subgraph of Two graphs are isomorphic if there is a correspondence between their vertex sets that preserves adjacency.
Basic routing, however, limits the traffic on the Ring Interval Graph, which is a spanning subgraph of the original graph.
ns](H) where H is a spanning subgraph of G, (iii) [[gamma].
A spanning subgraph of G has the same set V of vertices.
A graph H is a spanning subgraph of G if V(H) = V(G) and E(H) [subset or equal to] E(G).
We apply this to prove that, for every d [greater than or equal to] 7 and every k, where 7 [less than or equal to] k [less than or equal to] d, the d-dimensional hypercube contains a k-regular spanning subgraph such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle.
We prove that this property also holds for sparse spanning regular subgraphs of the cubes: for every d [greater than or equal to] 7 and every k, where 7 [less than or equal to] k [less than or equal to] d, the d-dimensional hypercube contains a k-regular spanning subgraph such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle.
a spanning subgraph whose every connected component is a clique with at least 2 vertices.
Observation 1 Let G be a bridgeless graph and H be a bridgeless spanning subgraph of G.
One consequence of the above theorem is that the restriction, in part 1 of the definition of a starter-matrix class C, that S be a labelled, induced subgraph of each element of C can be relaxed to S being a labelled subgraph of every graph in the collection: take the union of the starter-matrix classes such that S is a spanning subgraph of the starter graph for the class.

Site: Follow: Share:
Open / Close