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.103654License: CC BY

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 = "The first author was supported by the Institute for Basic Science (IBS-R029-Y3).The second, third, and fourth authors were supported by the Institute for Basic Science (IBS-R029-C1).Additionally the third author was supported by the EPSRC grant, United Kingdom no EP/S00100X/1 (A. Methuku)Additionally the fourth author was supported by NKFIH grantK135800.The last author was supported by the NSFC grant No.11871055.",

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

N1 - The first author was supported by the Institute for Basic Science (IBS-R029-Y3).The second, third, and fourth authors were supported by the Institute for Basic Science (IBS-R029-C1).Additionally the third author was supported by the EPSRC grant, United Kingdom no EP/S00100X/1 (A. Methuku)Additionally the fourth author was supported by NKFIH grantK135800.The last author was supported by the NSFC grant No.11871055.

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

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

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