Article ID Journal Published Year Pages File Type
9513475 Discrete Mathematics 2005 21 Pages PDF
Abstract
Let G and H be graphs. A substitution of H in G replacing a vertexv∈V(G) is the graph G(v→H) consisting of disjoint union of H and G-v with the additional edge-set {xy:x∈V(H),y∈NG(v)}. For a class of graphs P, its substitutional closureP* consists of all graphs that can be obtained from graphs of P by repeated substitutions. We apply the reducing pseudopath method (Discrete Appl. Math. 128 (2-3) (2003) 487-509) to characterize the substitutional closure of the class of basic graphs in terms of forbidden induced subgraphs.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,