Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9513475 | Discrete Mathematics | 2005 | 21 Pages |
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
Igor E. Zverovich, Vadim E. Zverovich,