An extremal problem on the potentially wheel graph sequences

被引：0

作者：

Chen, Gang ^{[1
,2
]}

Zhang, Qiang ^{[1
]}

机构：

[1] Beijing Inst Technol, Sch Management & Econ, Beijing 100081, Peoples R China

[2] Ningxia Univ, Dept Math, Ningxia 750021, Peoples R China

来源：

UTILITAS MATHEMATICA | 2017年 / 104卷

基金：

中国国家自然科学基金;

关键词：

graph; degree sequence; potentially W-r-graphic sequence; LEHEL CONJECTURE; REALIZATION; JACOBSON; ERDOS;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Gould, Jacobson and Lehel considered a variation of the classical Turan-type extremal problems: for a given graph H, determine the smallest even integer sigma(H,n) such that every n-term graphic sequence pi = (d(1), d(2),...,d(n)) with sigma(pi) = d(1) + d(2) + ... + d(n) >= sigma(H,n) has a realization G containing H as a subgraph. In this paper, we determine the values of sigma(W-r,n) for r >= 6 and n sufficiently large, where Wr is the wheel graph on r vertices.

引用

页码：3 / 13

页数：11

共 15 条

[1]

Chen G., 2003, J. XuZhou Normal University, V21, P5

[2]

Erdos P., 1960, Mat. Lapok (N.S.), V11, P264

[3]

Erdos P., 1991, Graphs realizing the same degree sequence and their respective clique numbers, graph theory, combinatorics and applications, Vi, P439

[4]

Gould R.J., 1999, Combinatorics, graph theory, and algorithms, V2, P451

[5]

Kleitman D. J., 1973, Discrete Mathematics, V6, P79, DOI 10.1016/0012-365X(73)90037-X

[6]

Lai C., 1997, J. ZhangZhou Teach. Coll. Nat. Sci, V11, P27

[7]

Lai C., 2004, J. Combin. Math. Combin. Comput, V49, P57

[8] The threshold for the Erdos, Jacobson and Lehel conjecture to be true [J].

Li, Jiong Sheng ;

Yin, Jian Hua .

ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2006, 22 (04) :1133-1138

[9] The Erdos-Jacobson-Lehel conjecture on potentially Pk-graphic sequence is true [J].

Li, JS ;

Song, ZX ;

Luo, R .

SCIENCE IN CHINA SERIES A-MATHEMATICS PHYSICS ASTRONOMY, 1998, 41 (05) :510-520

[10] An extremal problem on the potentially Pk-graphic sequences [J].

Li, JS ;

Song, ZX .

DISCRETE MATHEMATICS, 2000, 212 (03) :223-231

← 1 2 →