报告题目：Flow Polynomials of a Signed Graph

主 讲 人：钱 建 国

单 位：厦门大学

时 间：8月9日9:00

腾 讯 ID：266 000 199

密 码：无

摘 要：

In contrast to ordinary graphs, the number of the nowhere-zero group-flows in a signed graph may vary with different groups, even if the groups have the same order. In fact, for a signed graphGand non-negative integerd, it was shown that there exists a polynomialF_d(G,x) such that the number of the nowhere-zero Γ-flows inGequalsF_d(G,x) evaluated atkfor every Abelian group Γ of orderkwith ε(Γ) =d, where ε(Γ) is the largest integerdfor which Γ has a subgroup isomorphic toZ^d2.

In this talk, we introduce some results related to the interconnection among Γ-flows and the coefficients inF_d(G,x) for signed graphs. We first define the fundamental circuits for a signed graphGand show that all Γ-flows (not necessarily nowhere-zero) inGcan be generated by these circuits. Moreover, we show that all Γ-flows inGcan be evenly classified into 2^d-classes specified by the elements of order 2 in Γ, each class of which consists of the same number of flows depending only on the order of the group. This gives an explanation for why the number of the Γ-flows (nowhere-zero or not) in a signed graph varies with different ε(Γ) and also gives an answer to a problem posed by Beck and Zaslavsky. Further, using an extension of Whitney's broken circuit theory we give a combinatorial interpretation of the coefficients inF_d(G,x) ford= 0, in terms of the broken bonds. As an example, we give an analytic expression ofF₀(G,x) for a class of the signed graphs which contain no balanced circuit. Finally, we show that the broken bonds in a signed graph form a homogeneous simplicial complex.

简 介：

钱建国，厦门大学数学科学学院教授，博士生导师，主要从事图论应用（化学图论、网络拓扑结构设计与优化）及组合计数方面的研究。现任中国组合数学与图论专业委员会委员，中国运筹学会图论分会常务理事，福建省运筹学会副理事长。美国数学会《数学评论》评论员，发表评论40余篇；主持和参加多项国家面上及重点基金项目；在包括J. Combin. Theory (Ser A, Ser B) 及 J. Graph Theory等在内的国内外专业期刊上发表学术论文60余篇。