Asymptotic results on saturated graphs

Miroslaw Truszczynski, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Let F be a given graph. A graph G is called F-saturated if F [nsube] G and F ⊆ G + e for every edge e ∉ E(G), e ⊆ V(G). Denote by sat(n, F) the minimum number of edges in an F-saturated graph on n vertices. A conjecture of the second author states that limn→∞ sat(n, F)/n exists for every F. We characterize the case when the limit exists and is smaller than 1.

Original languageEnglish
Pages (from-to)309-314
Number of pages6
JournalDiscrete Mathematics
Volume87
Issue number3
DOIs
StatePublished - Feb 22 1991

Bibliographical note

Funding Information:
* Research supported in part by University of the Hungarian Academy of Sciences.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Asymptotic results on saturated graphs'. Together they form a unique fingerprint.

Cite this