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.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
Mentioned in ?
References in periodicals archive ?
G = (X, Y, Z) is a bipolar neutrosophic incidence tree if and only if bipolar neutrosophic incidence spanning subgraph H = (X, Y*, Z*) of G = (X, Y, Z) is a tree such that
Indeed, any realization of [pi] has only even sized components, hence, G cannot contain it as a spanning subgraph.
A spanning subgraph of a graph G is a subgraph H with V(H) = V(G).
Then a(G) = 2 if and only if [G.sup.*] contains a connected Eulerian spanning subgraph.
If [V.sub.s] = V, [E.sub.s] [subset or equal to] E, [G.sub.s]([V.sub.s], [E.sub.s], [A.sub.s]) is called a spanning subgraph. We say [G.sub.s]([V.sub.s], [E.sub.s], [A.sub.s]) is induced by [V.sub.s], if, for any ([v.sub.i], [v.sub.j]) [member of] [E.sub.s], ([v.sub.i], [v.sub.j]) [member of] [E.sub.s] [??] ([v.sub.i], [v.sub.j]) [member of] E.
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.
(2) G is called an intuitionistic fuzzy forest if G has an intuitionistic fuzzy spanning subgraph H = (A, C) which is a forest such that, for all (u, v) [member of] E - W, [[mu].sub.B](u, v) < [[mu].sup.[infinity].sub.C](u, v) and [v.sub.B](u, v) > [v.sup.[infinity].sub.C](u, v).
We say that [D.sub.0] = ([V.sub.0], [E.sub.0]) is a spanning subgraph of D if [V.sub.0] = V and [E.sub.0] [subset or equal to] E.
Basic routing, however, limits the traffic on the Ring Interval Graph, which is a spanning subgraph of the original graph.
Theorem 2.6 [8] For any connected graph G, (i)[gamma](G) [less than or equal to] [[gamma].sub.ns](G), (ii) [[gamma].sub.ns](G) [less than or equal to] [[gamma].sub.ns](H) where H is a spanning subgraph of G, (iii) [[gamma].sub.ns](G) [less than or equal to] (q - 2p + 1)/2 and (iv) [[gamma].sub.ns](G) [less than or equal to] p - [omega](G) + 1 where [omega](G) is the clique number of G.
A spanning subgraph of G has the same set V of vertices.