Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T22:17:13.740Z Has data issue: false hasContentIssue false

Isomorphic subgraphs having minimal intersections

Published online by Cambridge University Press:  09 April 2009

R. C. Mullin
Affiliation:
University of Waterloo Waterloo, Ontario, Canada
B. K. Roy
Affiliation:
University of Waterloo Waterloo, Ontario, Canada
P. J. Schellenberg
Affiliation:
University of Waterloo Waterloo, Ontario, Canada
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Given a finite graph H and G, a subgraph of it, we define σ (G, H) to be the largest integer such that every pair of subgraphs of H, both isomorphic to G, has at least σ(G, H) edges in common; furthermore, R(G, H) is defined to be the maximum number of subgraphs of H, all isomorphic to G, such that any two of them have σ(G, H) edges common between them. We are interested in the values of σ(G, H) and R(G, H) for general H and G. A number of combinatorial problems can be considered as special cases of this question; for example, the classical set-packing problem is equivalent to evaluating R (G, H) where G is a complete subgraph of the complete graph H and σ(G, H) = 0, and the decomposition of H into subgraphs isomorphic to G is equivalent to showing that σ(G, H) = 0 and R(G, H) = ε(H)/ε(G) where ε(H), ε(G) are the number of edges in H, G respectively.

A result of S. M. Johnson (1962) gives an upper bound for R(G, H) in terms of σ(G, H). As a corollary of Johnson's result, we obtain the upper bound of McCarthy and van Rees (1977) for the Cordes problem. The remainder of the paper is a study of σ (G, H) and R(G, H) for special classes of graphs; in particular, H is a complete graph and G is, in most instances, a union of disjoint complete subgraphs.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1983