On the unimodality of independence polynomials of some graphs

被引：38

作者：

Wang, Yi ^{[1
]}

Zhu, Bao-Xuan ^{[1
]}

机构：

[1] Dalian Univ Technol, Sch Math Sci, Dalian 116024, Peoples R China

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2011年 / 32卷 / 01期

基金：

美国国家科学基金会;

关键词：

CHROMATIC POLYNOMIALS; ROOTS; CONJECTURE; SEQUENCES; LOCATION;

D O I：

10.1016/j.ejc.2010.08.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we study unimodality problems for the independence polynomial of a graph, including unimodality, log-concavity and reality of zeros. We establish recurrence relations and give factorizations of independence polynomials for certain classes of graphs. As applications we settle some unimodality conjectures and problems. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：10 / 20

页数：11

共 41 条

[1]

Alavi Y., 1987, Congr. Numer., V58, P15

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[3]

[Anonymous], 2010, Matroid theory

[4]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[5] On linear transformations preserving the Polya frequency property [J].

Branden, Petter .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2006, 358 (08) :3697-3716

[6] LOCATION OF ZEROS OF CHROMATIC AND RELATED POLYNOMIALS OF GRAPHS [J].

BRENTI, F ;

ROYLE, GF ;

WAGNER, DG .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1994, 46 (01) :55-80

[7] EXPANSIONS OF CHROMATIC POLYNOMIALS AND LOG-CONCAVITY [J].

BRENTI, F .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1992, 332 (02) :729-756

[8]

Brenti F., 1994, Contemp. Math., V178, P417

[9]

Brenti F., 1989, Mem. Am. Math. Soc., V413

[10] Roots of independence polynomials of well covered graphs [J].

Brown, JI ;

Dilcher, K ;

Nowakowski, RJ .

JOURNAL OF ALGEBRAIC COMBINATORICS, 2000, 11 (03) :197-210

← 1 2 3 4 5 →