Flow polynomials of a signed graph

被引:0
|
作者
Ren, Xiangyu [1 ]
Qian, Jianguo [1 ]
机构
[1] Xiamen Univ, Sch Math Sci, Xiamen 361005, Fujian, Peoples R China
来源
ELECTRONIC JOURNAL OF COMBINATORICS | 2019年 / 26卷 / 03期
关键词
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
For a signed graph G and non-negative integer d, it was shown by DeVos et al. that there exists a polynomial F-d(G, x) such that the number of the nowhere-zero Gamma-flows in G equals F-d(G, x) evaluated at k for every Abelian group Gamma of order k with epsilon(Gamma) = d, where epsilon(Gamma) is the largest integer d for which Gamma has a subgroup isomorphic to Z(2)(d). We define a class of particular directed circuits in G, namely the fundamental directed circuits, and show that all Gamma-flows (not necessarily nowhere-zero) in G can be generated by these circuits. It turns out that all Gamma-flows in G can be evenly partitioned into 2(epsilon)((Gamma)) classes specified by the elements of order 2 in Gamma, each class of which consists of the same number of flows depending only on the order of Gamma. Using an extension of Whitney's broken circuit theorem of Dohmen and Trinks, we give a combinatorial interpretation of the coefficients in F-d(G, x) for d = 0 in terms of broken bonds. Finally, we show that the sets of edges in a signed graph that contain no broken bond form a homogeneous simplicial complex.
引用
收藏
页数:16
相关论文
共 50 条
  • [41] Remarks on the Largest Eigenvalue of a Signed Graph
    Lan, Kaiyang
    Li, Jianxi
    Liu, Feng
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2023, 46 (05)
  • [42] Signed star domatic number of a graph
    Atapour, M.
    Sheikholeslami, S. M.
    Ghameshlou, A. N.
    Volkmann, L.
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (03) : 213 - 218
  • [43] Signed Bipartite Graph Neural Networks
    Huang, Junjie
    Shen, Huawei
    Cao, Qi
    Tao, Shuchang
    Cheng, Xueqi
    PROCEEDINGS OF THE 30TH ACM INTERNATIONAL CONFERENCE ON INFORMATION & KNOWLEDGE MANAGEMENT, CIKM 2021, 2021, : 740 - 749
  • [44] On the inertia set of a signed graph with loops
    Arav, Marina
    van der Holst, Hein
    Sinkovic, John
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2015, 471 : 169 - 183
  • [45] CHARACTERIZATION OF THE MAXIMUM GENUS OF A SIGNED GRAPH
    SIRAN, J
    SKOVIERA, M
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 52 (01) : 124 - 146
  • [46] Signed Laplacian Graph Neural Networks
    Li, Yu
    Qu, Meng
    Tang, Jian
    Chang, Yi
    THIRTY-SEVENTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 37 NO 4, 2023, : 4444 - 4452
  • [47] The signed Roman domatic number of a graph
    Sheikholeslami, Seyed Mahmoud
    Volkmann, Lutz
    ANNALES MATHEMATICAE ET INFORMATICAE, 2012, 40 : 105 - 112
  • [48] Is there a matroid theory of signed graph embedding?
    Zaslavsky, T
    ARS COMBINATORIA, 1997, 45 : 129 - 141
  • [49] Signed total domination number of a graph
    Zelinka, B
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2001, 51 (02) : 225 - 229
  • [50] ON THE REGULARITY OF SOME SIGNED GRAPH STRUCTURES
    Sinha, Deepa
    Garg, Pravin
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2011, 8 (01) : 63 - 74