On the independence number of graphs related to a polarity

Sam Mattheus; Francesco Pavese; Leo Storme

doi:10.1002/jgt.22442

On the independence number of graphs related to a polarity

Sam Mattheus, Francesco Pavese, Leo Storme

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

2 Citations (Scopus)

Abstract

We investigate the independence number of two graphs constructed from a polarity of PG(2, q). For the first graph under consideration, the Erdős-Rényi graph E, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper, we consider the Erdős-Rényi hypergraph of triangles H _q. We determine the exact magnitude of the independence number of H _q, q even. This solves a problem posed by Mubayi and Williford [On the independence number of the ErdŐs-RÉnyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113-127, Open Problem 3].

Original language	English
Pages (from-to)	96-110
Number of pages <span style="color:red"p> <font size="1.5"> ✽ </span> </font>	15
Journal	Journal of Graph Theory
Volume	92
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22442
Publication status	Published - 12 Dec 2018

Keywords

Erdős-Rényi graph
independence number
polarity graph

Access to Document

10.1002/jgt.22442

Cite this

@article{d8922ad84de44f4d934281e57447a855,

title = "On the independence number of graphs related to a polarity",

abstract = "We investigate the independence number of two graphs constructed from a polarity of PG(2, q). For the first graph under consideration, the Erd{\H o}s-R{\'e}nyi graph E, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper, we consider the Erd{\H o}s-R{\'e}nyi hypergraph of triangles H q. We determine the exact magnitude of the independence number of H q, q even. This solves a problem posed by Mubayi and Williford [On the independence number of the Erd{\H O}s-R{\'E}nyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113-127, Open Problem 3]. ",

keywords = "Erd{\H o}s-R{\'e}nyi graph, independence number, polarity graph",

author = "Sam Mattheus and Francesco Pavese and Leo Storme",

year = "2018",

month = dec,

day = "12",

doi = "10.1002/jgt.22442",

language = "English",

volume = "92",

pages = "96--110",

journal = "Journal of Graph Theory",

issn = "1097-0118",

publisher = "Wiley , John Wiley & Sons,",

number = "2",

}

TY - JOUR

T1 - On the independence number of graphs related to a polarity

AU - Mattheus, Sam

AU - Pavese, Francesco

AU - Storme, Leo

PY - 2018/12/12

Y1 - 2018/12/12

N2 - We investigate the independence number of two graphs constructed from a polarity of PG(2, q). For the first graph under consideration, the Erdős-Rényi graph E, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper, we consider the Erdős-Rényi hypergraph of triangles H q. We determine the exact magnitude of the independence number of H q, q even. This solves a problem posed by Mubayi and Williford [On the independence number of the ErdŐs-RÉnyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113-127, Open Problem 3].

AB - We investigate the independence number of two graphs constructed from a polarity of PG(2, q). For the first graph under consideration, the Erdős-Rényi graph E, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper, we consider the Erdős-Rényi hypergraph of triangles H q. We determine the exact magnitude of the independence number of H q, q even. This solves a problem posed by Mubayi and Williford [On the independence number of the ErdŐs-RÉnyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113-127, Open Problem 3].

KW - Erdős-Rényi graph

KW - independence number

KW - polarity graph

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

U2 - 10.1002/jgt.22442

DO - 10.1002/jgt.22442

M3 - Article

VL - 92

SP - 96

EP - 110

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 1097-0118

IS - 2

ER -

On the independence number of graphs related to a polarity

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this