On Circulants Uniquely Characterized by their Independence Polynomials

被引：0

作者：

Brown, Jason ^{[1
]}

Hoshino, Richard ^{[1
]}

机构：

[1] Dalhousie Univ, Dept Math & Stat, Halifax, NS B3H 3J5, Canada

来源：

ARS COMBINATORIA | 2012年 / 104卷

关键词：

circulant graph; matching polynomial; chromatic polynomial; independence polynomial; threshold graphs; spider graphs; GRAPHS; ISOMORPHISM; CONJECTURE;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In [18], Farrell and Whitehead investigate circulant graphs that are uniquely characterized by their matching and chromatic polynomials (i.e., graphs that are "matching unique" and "chromatic unique"). They develop a partial classification theorem, by finding all matching unique and chromatic unique circulants on n vertices, for each n <= 8. In this paper, we explore circulant graphs that are uniquely characterized by their independence polynomials. We obtain a full classification theorem by proving that a circulant is independence unique if it is the disjoint union of isomorphic complete graphs.

引用

页码：363 / 374

页数：12

共 38 条

[21] ON THE VALUES OF INDEPENDENCE AND DOMINATION POLYNOMIALS AT SPECIFIC POINTS
Alikhani, S.
Reyhani, M. H.
TRANSACTIONS ON COMBINATORICS, 2012, 1 (02) : 49 - 57
[22] Clique cover products and unimodality of independence polynomials
Zhu, Bao-Xuan
DISCRETE APPLIED MATHEMATICS, 2016, 206 : 172 - 180
[23] Hypergraph independence polynomials with a zero close to the origin
Zhang, Shengtong
COMBINATORICS PROBABILITY AND COMPUTING, 2025,
[24] On the largest real root of independence polynomials of trees
Oboudi, Mohammad Reza
ARS COMBINATORIA, 2018, 137 : 149 - 164
[25] Unimodality of the Independence Polynomials of Some Composite Graphs
Zhu, Bao-Xuan
Lu, Qinglin
FILOMAT, 2017, 31 (03) : 629 - 637
[26] Computing the matching and independence polynomials of double hexagonal chains
Chen, Hanlin
Guo, Qiuzhi
Tan, Yihong
DISCRETE APPLIED MATHEMATICS, 2025, 363 : 139 - 157
[27] Independence Number and Maximal Chromatic Polynomials of Connected Graphs
Long, Shude
Cai, Junliang
GRAPHS AND COMBINATORICS, 2024, 40 (05)
[28] Independence polynomials of k-tree related graphs
Song, Lanzhen
Staton, William
Wei, Bing
DISCRETE APPLIED MATHEMATICS, 2010, 158 (08) : 943 - 950
[29] Maximal trees with log-concave independence polynomials
Mandrescu, Eugen
Spivak, Alexander
NOTES ON NUMBER THEORY AND DISCRETE MATHEMATICS, 2016, 22 (02) : 44 - 53
[30] Independence polynomials of graphs with given cover number or dominate number
Cui, Yu-Jie
Zhu, Aria Mingyue
Zhan, Xin-Chun
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025, 17 (01)

← 1 2 3 4 →