Measures on monotone properties of graphs

Jòzsef Balogh; Béla Bollobás; David Weinreich

doi:10.1016/S0166-218X(01)00175-5

Measures on monotone properties of graphs

Jòzsef Balogh, Béla Bollobás, David Weinreich

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

Abstract

Given a monotone property P of graphs, write P ⁿ for the set of graphs with vertex set [n] having property P. Building on recent results in the enumeration of graphical properties, we prove numerous results about the structure of graphs in P ⁿ and the functions |P ⁿ|. We also examine the measure eP(n), the maximum number of edges in a graph of P ⁿ.

Original language	English (US)
Pages (from-to)	17-36
Number of pages	20
Journal	Discrete Applied Mathematics
Volume	116
Issue number	1-2
DOIs	https://doi.org/10.1016/S0166-218X(01)00175-5
State	Published - Jan 15 2002
Externally published	Yes

Keywords

Extremal graph theory
Graph properties
Hereditary
Monotone
Size
Speed

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.1016/S0166-218X(01)00175-5

Library availability

Discover UIUC Full Text

Cite this

@article{74993165648b4d39aecf6fae946997b4,

title = "Measures on monotone properties of graphs",

abstract = "Given a monotone property P of graphs, write P n for the set of graphs with vertex set [n] having property P. Building on recent results in the enumeration of graphical properties, we prove numerous results about the structure of graphs in P n and the functions |P n|. We also examine the measure eP(n), the maximum number of edges in a graph of P n.",

keywords = "Extremal graph theory, Graph properties, Hereditary, Monotone, Size, Speed",

author = "J{\`o}zsef Balogh and B{\'e}la Bollob{\'a}s and David Weinreich",

note = "Funding Information: Research partially supported by OTKA grant F026049 and NSF Grant DMS 9971788. ",

year = "2002",

month = jan,

day = "15",

doi = "10.1016/S0166-218X(01)00175-5",

language = "English (US)",

volume = "116",

pages = "17--36",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1-2",

}

TY - JOUR

T1 - Measures on monotone properties of graphs

AU - Balogh, Jòzsef

AU - Bollobás, Béla

AU - Weinreich, David

N1 - Funding Information: Research partially supported by OTKA grant F026049 and NSF Grant DMS 9971788.

PY - 2002/1/15

Y1 - 2002/1/15

N2 - Given a monotone property P of graphs, write P n for the set of graphs with vertex set [n] having property P. Building on recent results in the enumeration of graphical properties, we prove numerous results about the structure of graphs in P n and the functions |P n|. We also examine the measure eP(n), the maximum number of edges in a graph of P n.

AB - Given a monotone property P of graphs, write P n for the set of graphs with vertex set [n] having property P. Building on recent results in the enumeration of graphical properties, we prove numerous results about the structure of graphs in P n and the functions |P n|. We also examine the measure eP(n), the maximum number of edges in a graph of P n.

KW - Extremal graph theory

KW - Graph properties

KW - Hereditary

KW - Monotone

KW - Size

KW - Speed

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

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

U2 - 10.1016/S0166-218X(01)00175-5

DO - 10.1016/S0166-218X(01)00175-5

M3 - Article

AN - SCOPUS:84867957342

SN - 0166-218X

VL - 116

SP - 17

EP - 36

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-2

ER -

Measures on monotone properties of graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this