Abstract
A graph israndomly matchable if every matching of the graph is contained in a perfect matching. We generalize this notion and say that a graphG israndomly H-coverable if every set of independent subgraphs, each isomorphic toH, that does not cover the vertices ofG can be extended to a larger set of independent copies ofH.
Various problems are considered for the situation whereH is a path. In particular, we characterize the graphs that are randomlyP 3 -coverable.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Behzad, G. Chartrand andL. Lesniak-Foster,Graphs and digraphs, Prindle, Weber and Schmidt, Boston, 1979.MR 80f: 05019
G. Chartrand andH. V. Kronk, Randomly traceable graphs,SIAM J. Appl. Math. 16 (1968), 696–700.MR 38: 3166
D. P. Sumner, Randomly matchable graphs,J. Graph Theory 3 (1979), 183–186.MR 80k: 05088
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Fink, J.F., Jacobson, M.S., Kinch, L.F. et al. RandomlyH-coverable graphs. Period Math Hung 16, 15–22 (1985). https://doi.org/10.1007/BF01855800
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01855800