# induced subgraph

## induced subgraph

[in‚düst ′səb‚graf]
(mathematics)
vertex-induced subgraph
Mentioned in ?
References in periodicals archive ?
Note that if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains in particular all edges of the induced subgraph G[X] of G on X.
A dominating set S of a graph G without isolated vertices is called the neighborhood total dominating set (ntd-set) if the induced subgraph N(S) has no isolated vertices.
For a subgraph H of a graph G, G-H denotes the induced subgraph by V(G) - V(H), and G[S] denotes the induced subgraph by S for S [subset or equal to] V(G).
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.
Acharya, Germina, and Ajitha [1] have shown that every graph can be embedded as an induced subgraph of a strongly multiplicative graph.
A graph is called claw-free if it has no induced subgraph isomorphic to [K.
Let us draw the induced subgraph of the graph G1 (of the graph G2 respectively) containing the vertex 6 (the vertex Me respectively) and its neighbors (see Figure 18).
A dominating set D of a graph G is said to be split and non-split dominating set if the induced subgraph <V\D> disconnected and <V\D> connected respectively.
If the induced subgraph of is connected, then is a connected dominating set (CDS).
An intersection graph of a set of 2 x 2 dense blocks is an induced subgraph of the so called X-grid which consists of the usual 2 dimensional grid, and diagonals for each grid square.
The induced subgraph on the neighbors of i is vector (k - 1)-colorable.
For every graph H there is a constant [sigma] > 0 such that every graph on n vertices which does not contain H as an induced subgraph has a clique or independent set of size at least [n.

Site: Follow: Share:
Open / Close