Premium
Reconstructing the number of copies of a valency‐labeled finite graph in an infinite graph
Author(s) -
King A. J. H.,
NashWilliams C. St. J. A.
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180202
Subject(s) - combinatorics , mathematics , valency , bijection , vertex (graph theory) , graph , finite set , vertex connectivity , discrete mathematics , finite graph , induced subgraph , mathematical analysis , philosophy , linguistics
Suppose that G, H are infinite graphs and there is a bijection Ψ; V(G) Ψ V(H) such that G ‐ ξ ≅ H ‐ Ψ(ξ) for every ξ ∼ V (G). Let J be a finite graph and /(π) be a cardinal number for each π ≅ V (J). Suppose also that either /(π) is infinite for every π ≅ V (J) or J has a connected subgraph C such that /(π) is finite for every π ≅ V (C) and every vertex in V(J)/V(C) is adjacent to a vertex of C. Let (J, I, G) be the set of those subgraphs of G that are isomorphic to J under isomorphisms that map each vertex π of J to a vertex whose valency in G is /(π). We prove that the sets (J, I, G), m(J, I, H) have the same cardinality and include equal numbers of induced subgraphs of G, H respectively.