Generalized Turán numbers for the edge blow-up of a graph

Zequn Lv; Ervin Győri; Zhen He; Nika Salia; Casey Tompkins; Kitti Varga; Xiutao Zhu

doi:10.1016/j.disc.2023.113682

Generalized Turán numbers for the edge blow-up of a graph

Zequn Lv
, Ervin Győri
, Zhen He^*
, Nika Salia
, Casey Tompkins
, Kitti Varga
, Xiutao Zhu

^*Corresponding author for this work

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

4 Scopus citations

Abstract

Let H be a graph and p be an integer. The edge blow-up H^p of H is the graph obtained from replacing each edge in H by a copy of K_p where the new vertices of the cliques are all distinct. Let C_k and P_k denote the cycle and path with k vertices, respectively. In this paper, we find sharp upper bounds for ex(n,K₃,C₃ ³) and the exact value for ex(n,K₃,P₄ ³). Moreover, we determine the graphs attaining these bounds.

Original language	English
Article number	113682
Journal	Discrete Mathematics
Volume	347
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2023.113682
State	Published - Jan 2024
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2023 Elsevier B.V.

Keywords

Blow-up graph
Extremal problems
Turan number

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2023.113682

Cite this

@article{db15b232cc27425bb2879c001b0c5d24,

title = "Generalized Tur{\'a}n numbers for the edge blow-up of a graph",

abstract = "Let H be a graph and p be an integer. The edge blow-up Hp of H is the graph obtained from replacing each edge in H by a copy of Kp where the new vertices of the cliques are all distinct. Let Ck and Pk denote the cycle and path with k vertices, respectively. In this paper, we find sharp upper bounds for ex(n,K3,C3 3) and the exact value for ex(n,K3,P4 3). Moreover, we determine the graphs attaining these bounds.",

keywords = "Blow-up graph, Extremal problems, Turan number",

author = "Zequn Lv and Ervin Gy{\H o}ri and Zhen He and Nika Salia and Casey Tompkins and Kitti Varga and Xiutao Zhu",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2024",

month = jan,

doi = "10.1016/j.disc.2023.113682",

language = "English",

volume = "347",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier BV",

number = "1",

}

TY - JOUR

T1 - Generalized Turán numbers for the edge blow-up of a graph

AU - Lv, Zequn

AU - Győri, Ervin

AU - He, Zhen

AU - Salia, Nika

AU - Tompkins, Casey

AU - Varga, Kitti

AU - Zhu, Xiutao

PY - 2024/1

Y1 - 2024/1

N2 - Let H be a graph and p be an integer. The edge blow-up Hp of H is the graph obtained from replacing each edge in H by a copy of Kp where the new vertices of the cliques are all distinct. Let Ck and Pk denote the cycle and path with k vertices, respectively. In this paper, we find sharp upper bounds for ex(n,K3,C3 3) and the exact value for ex(n,K3,P4 3). Moreover, we determine the graphs attaining these bounds.

AB - Let H be a graph and p be an integer. The edge blow-up Hp of H is the graph obtained from replacing each edge in H by a copy of Kp where the new vertices of the cliques are all distinct. Let Ck and Pk denote the cycle and path with k vertices, respectively. In this paper, we find sharp upper bounds for ex(n,K3,C3 3) and the exact value for ex(n,K3,P4 3). Moreover, we determine the graphs attaining these bounds.

KW - Blow-up graph

KW - Extremal problems

KW - Turan number

UR - https://www.scopus.com/pages/publications/85169845083

U2 - 10.1016/j.disc.2023.113682

DO - 10.1016/j.disc.2023.113682

M3 - Article

AN - SCOPUS:85169845083

SN - 0012-365X

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

M1 - 113682

ER -

Generalized Turán numbers for the edge blow-up of a graph

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this