Connectedness, Classes and Cycle Index

E. A. Bender, P. J. Cameron, A. M. Odlyzko, L. B. Richmond

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

This paper begins with the observation that half of all graphs containing no induced path of length 3 are disconnected. We generalize this in several directions. First, we give necessary and sufficient conditions (in terms of generating functions) for the probability of connectedness in a suitable class of graphs to tend to a limit strictly between zero and one. Next we give a general framework in which this and related questions can be posed, involving operations on classes of finite structures. Finally, we discuss briefly an algebra associated with such a class of structures, and give a conjecture about its structure.

Original languageEnglish (US)
Pages (from-to)31-43
Number of pages13
JournalCombinatorics Probability and Computing
Volume8
Issue number1-2
DOIs
StatePublished - Jan 1 1999
Externally publishedYes

Fingerprint Dive into the research topics of 'Connectedness, Classes and Cycle Index'. Together they form a unique fingerprint.

Cite this