Edge cut splitting formulas for Tutte-Grothendieck invariants

被引：1
作者：
Kochol, Martin [1 ]
机构：
[1] MU SAV, Stefanikova 49, Bratislava 81473 1, Slovakia
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2017年 / 125卷
关键词：
Isthmus-smooth Tutte-Grothendieck; invariant; Tutte polynomial; Matrix; Determinant; Partition; Bell number; Edge-cut; POLYNOMIALS; GRAPHS;
D O I：
10.1016/j.jctb.2017.03.004
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Tutte-Grothendieck invariants of graphs are mappings from a class of graphs to a commutative ring that are characterized recursively by contraction-deletion rules. Well known examples are the Tutte, chromatic, tension and flow polynomials. Suppose that an edge cut C divides a graph C into two parts G(1), G'(1) and that G(1), G'(1) are the sets of minors of G whose edge sets consist of C and edges of G(1), G'(1), respectively. We study determinant formulas evaluating a Tutte-Grothendieck invariant of C from the Tutte-Grothendieck invariants of graphs from G(1) and G'(1) (C) 2017 Elsevier Inc. All rights reserved.
引用
收藏
页码：114 / 131
页数：18
相关论文
共 24 条
[1]  
Aigner M., 1979, COMBINATORIAL THEORY
[2]   Splitting formulas for Tutte polynomials [J].
Andrzejak, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 70 (02) :346-366
[3]   THE COMPLEXITIES OF THE COEFFICIENTS OF THE TUTTE POLYNOMIAL [J].
ANNAN, JD .
DISCRETE APPLIED MATHEMATICS, 1995, 57 (2-3) :93-103
[4]  
[Anonymous], 2013, Modern graph theory
[5]   A little statistical mechanics for the graph theorist [J].
Beaudin, Laura ;
Ellis-Monaghan, Joanna ;
Pangborn, Greta ;
Shrock, Robert .
DISCRETE MATHEMATICS, 2010, 310 (13-14) :2037-2053
[6]   Tutte polynomials of bracelets [J].
Biggs, Norman .
JOURNAL OF ALGEBRAIC COMBINATORICS, 2010, 32 (03) :389-398
[7]   Transfer matrices for the partition function of the Potts model on lattice strips with toroidal and Klein-bottle boundary conditions [J].
Chang, SC ;
Shrock, R .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2006, 364 :231-262
[8]   Dual complementary polynomials of graphs and combinatorial-geometric interpretation on the values of Tutte polynomial at positive integers [J].
Chen, Beifang .
EUROPEAN JOURNAL OF COMBINATORICS, 2014, 36 :206-230
[9]  
Crapo H.H., 1969, Aequ. Math., V3, P211, DOI [10.1007/bf01817442, DOI 10.1007/BF01817442]
[10]   Inapproximability of the Tutte polynomial [J].
Goldberg, Leslie Ann ;
Jerrum, Mark .
INFORMATION AND COMPUTATION, 2008, 206 (07) :908-929
123