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 条
  • [31] An algorithm for calculating the independence and vertex-cover polynomials of a graph
    Cash, Gordon G.
    APPLIED MATHEMATICS AND COMPUTATION, 2007, 190 (02) : 1487 - 1491
  • [32] The Independence and Clique Polynomials of the Center Graphs of Some Finite Groups
    Najmuddin, Nabilah
    Sarmin, Nor Haniza
    Erfanian, A.
    SOUTHEAST ASIAN BULLETIN OF MATHEMATICS, 2020, 44 (06) : 803 - 812
  • [33] Building Graphs Whose Independence Polynomials Have Only Real Roots
    Eugen Mandrescu
    Graphs and Combinatorics, 2009, 25 : 545 - 556
  • [34] Building Graphs Whose Independence Polynomials Have Only Real Roots
    Mandrescu, Eugen
    GRAPHS AND COMBINATORICS, 2009, 25 (04) : 545 - 556
  • [35] Log-concavity of some independence polynomials via a partial ordering
    Bautista-Ramos, Cesar
    Guillen-Galvan, Carlos
    Gomez-Salgado, Paulino
    DISCRETE MATHEMATICS, 2019, 342 (01) : 18 - 28
  • [36] On the roots of independence polynomials of almost all very well-covered graphs
    Levit, Vadim E.
    Mandrescu, Eugen
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (04) : 478 - 491
  • [37] Independence polynomials and the unimodality conjecture for very well-covered, quasi-regularizable, and perfect graphs
    Levit, Vadim E.
    Mandrescu, Eugen
    GRAPH THEORY IN PARIS: PROCEEDINGS OF A CONFERENCE IN MEMORY OF CALUDE BERGE, 2007, : 243 - +
  • [38] Log-concavity of some independence polynomials via a partial ordering (vol 342, pg 18, 2019)
    Bautista-Ramos, Cesar
    Guillen-Galvan, Carlos
    Gomez-Salgado, Paulino
    DISCRETE MATHEMATICS, 2023, 346 (12)
1234