Asymptotic results on saturated graphs

Miroslaw Truszczynski; Zsolt Tuza

doi:10.1016/0012-365X(91)90140-W

Asymptotic results on saturated graphs

Miroslaw Truszczynski, Zsolt Tuza

Computer Science

Research output: Contribution to journal › Article › peer-review

11 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 lim_n→∞ sat(n, F)/n exists for every F. We characterize the case when the limit exists and is smaller than 1.

Original language	English
Pages (from-to)	309-314
Number of pages	6
Journal	Discrete Mathematics
Volume	87
Issue number	3
DOIs	https://doi.org/10.1016/0012-365X(91)90140-W
State	Published - 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

Access to Document

10.1016/0012-365X(91)90140-W

Cite this

@article{2eb01d477e2b4a1aaad1302d9a227013,

title = "Asymptotic results on saturated graphs",

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.",

author = "Miroslaw Truszczynski and Zsolt Tuza",

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

year = "1991",

month = feb,

day = "22",

doi = "10.1016/0012-365X(91)90140-W",

language = "English",

volume = "87",

pages = "309--314",

number = "3",

}

TY - JOUR

T1 - Asymptotic results on saturated graphs

AU - Truszczynski, Miroslaw

AU - Tuza, Zsolt

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

PY - 1991/2/22

Y1 - 1991/2/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0042766744&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042766744&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(91)90140-W

DO - 10.1016/0012-365X(91)90140-W

M3 - Article

AN - SCOPUS:0042766744

SN - 0012-365X

VL - 87

SP - 309

EP - 314

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Asymptotic results on saturated graphs

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this