Counting cliques in 1-planar graphs

J. Pascal Gollin; Kevin Hendrey; Abhishek Methuku; Casey Tompkins; Xin Zhang

doi:10.1016/j.ejc.2022.103654

Counting cliques in 1-planar graphs

J. Pascal Gollin, Kevin Hendrey, Abhishek Methuku, Casey Tompkins, Xin Zhang

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

Abstract

The problem of maximising the number of cliques among n-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of 1-planar graphs where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems.

Original language	English (US)
Article number	103654
Journal	European Journal of Combinatorics
Volume	109
DOIs	https://doi.org/10.1016/j.ejc.2022.103654
State	Published - Mar 2023
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Online availability

10.1016/j.ejc.2022.103654

Library availability

Discover UIUC Full Text

Cite this

@article{ef5442cd6ea44a138fd08d3fc43c803e,

title = "Counting cliques in 1-planar graphs",

abstract = "The problem of maximising the number of cliques among n-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of 1-planar graphs where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems.",

author = "Gollin, {J. Pascal} and Kevin Hendrey and Abhishek Methuku and Casey Tompkins and Xin Zhang",

note = "Publisher Copyright: {\textcopyright} 2022 The Author(s)",

year = "2023",

month = mar,

doi = "10.1016/j.ejc.2022.103654",

language = "English (US)",

volume = "109",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Counting cliques in 1-planar graphs

AU - Gollin, J. Pascal

AU - Hendrey, Kevin

AU - Methuku, Abhishek

AU - Tompkins, Casey

AU - Zhang, Xin

PY - 2023/3

Y1 - 2023/3

N2 - The problem of maximising the number of cliques among n-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of 1-planar graphs where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems.

AB - The problem of maximising the number of cliques among n-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of 1-planar graphs where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems.

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

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

U2 - 10.1016/j.ejc.2022.103654

DO - 10.1016/j.ejc.2022.103654

M3 - Article

AN - SCOPUS:85144368308

SN - 0195-6698

VL - 109

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103654

ER -

Counting cliques in 1-planar graphs

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this