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

Producción científica: Article › revisión exhaustiva

11 Citas (Scopus)

Resumen

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.

Idioma original	English
Páginas (desde-hasta)	309-314
Número de páginas	6
Publicación	Discrete Mathematics
Volumen	87
N.º	3
DOI	https://doi.org/10.1016/0012-365X(91)90140-W
Estado	Published - feb 22 1991

Nota bibliográfica

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

Financiación

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

Financiadores
University of the Hungarian Academy of Sciences

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Acceder al documento

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

Otros archivos y enlaces

Citar esto

@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

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto