The Turán number of disjoint copies of paths

Long Tu Yuan; Xiao Dong Zhang

doi:10.1016/j.disc.2016.08.004

The Turán number of disjoint copies of paths

Long Tu Yuan, Xiao Dong Zhang^*

^*Corresponding author for this work

Shanghai Jiao Tong University

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

54 Scopus citations

Abstract

The Turán number of a graph H, denoted by ex(n,H), is the maximum number of edges in a simple graph of order n which does not contain H as a subgraph. In this paper, we determine the value ex(n,k⋅P₃) and characterize all extremal graphs for all positive integers n and k, where k⋅P₃ is k disjoint copies of a path on three vertices. This extends a result of Bushaw and Kettle (2011), which solved the conjecture proposed by Gorgol (2011).

Original language	English
Pages (from-to)	132-139
Number of pages	8
Journal	Discrete Mathematics
Volume	340
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2016.08.004
State	Published - 6 Feb 2017
Externally published	Yes

Keywords

Disjoint path
Extremal graph
Turán number

Access to Document

10.1016/j.disc.2016.08.004

Cite this

@article{ce5ad9d9b55346f7bf90716f78645e8a,

title = "The Tur{\'a}n number of disjoint copies of paths",

abstract = "The Tur{\'a}n number of a graph H, denoted by ex(n,H), is the maximum number of edges in a simple graph of order n which does not contain H as a subgraph. In this paper, we determine the value ex(n,k⋅P3) and characterize all extremal graphs for all positive integers n and k, where k⋅P3 is k disjoint copies of a path on three vertices. This extends a result of Bushaw and Kettle (2011), which solved the conjecture proposed by Gorgol (2011).",

keywords = "Disjoint path, Extremal graph, Tur{\'a}n number",

author = "Yuan, \{Long Tu\} and Zhang, \{Xiao Dong\}",

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

year = "2017",

month = feb,

day = "6",

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

language = "英语",

volume = "340",

pages = "132--139",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - The Turán number of disjoint copies of paths

AU - Yuan, Long Tu

AU - Zhang, Xiao Dong

PY - 2017/2/6

Y1 - 2017/2/6

N2 - The Turán number of a graph H, denoted by ex(n,H), is the maximum number of edges in a simple graph of order n which does not contain H as a subgraph. In this paper, we determine the value ex(n,k⋅P3) and characterize all extremal graphs for all positive integers n and k, where k⋅P3 is k disjoint copies of a path on three vertices. This extends a result of Bushaw and Kettle (2011), which solved the conjecture proposed by Gorgol (2011).

AB - The Turán number of a graph H, denoted by ex(n,H), is the maximum number of edges in a simple graph of order n which does not contain H as a subgraph. In this paper, we determine the value ex(n,k⋅P3) and characterize all extremal graphs for all positive integers n and k, where k⋅P3 is k disjoint copies of a path on three vertices. This extends a result of Bushaw and Kettle (2011), which solved the conjecture proposed by Gorgol (2011).

KW - Disjoint path

KW - Extremal graph

KW - Turán number

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

U2 - 10.1016/j.disc.2016.08.004

DO - 10.1016/j.disc.2016.08.004

M3 - 文章

AN - SCOPUS:84984820374

SN - 0012-365X

VL - 340

SP - 132

EP - 139

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

The Turán number of disjoint copies of paths

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this