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.

Funding

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

Funders
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 - https://www.scopus.com/pages/publications/0042766744

UR - https://www.scopus.com/pages/publications/0042766744#tab=citedBy

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

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this