报告题目: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 polynomialFd(G,x) such that the number of the nowhere-zero Γ-flows inGequalsFd(G,x) evaluated atkfor every Abelian group Γ of orderkwith ε(Γ) =d, where ε(Γ) is the largest integerdfor which Γ has a subgroup isomorphic toZd2.
In this talk, we introduce some results related to the interconnection among Γ-flows and the coefficients inFd(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 2d-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 inFd(G,x) ford= 0, in terms of the broken bonds. As an example, we give an analytic expression ofF0(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余篇。