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 条
  • [21] The Polynomials of a Graph
    Sedghi, S.
    Shobe, N.
    Salahshoor, M. A.
    IRANIAN JOURNAL OF MATHEMATICAL SCIENCES AND INFORMATICS, 2008, 3 (02): : 55 - 68
  • [22] HOW COLORFUL THE SIGNED GRAPH
    ZASLAVSKY, T
    DISCRETE MATHEMATICS, 1984, 52 (2-3) : 279 - 284
  • [23] Concepts of signed graph coloring
    Steffen, Eckhard
    Vogel, Alexander
    EUROPEAN JOURNAL OF COMBINATORICS, 2021, 91
  • [24] Computing the determinant of a signed graph
    Alshamary, Bader
    Stanic, Zoran
    OPEN MATHEMATICS, 2024, 22 (01):
  • [25] Signed Graph Convolutional Networks
    Derr, Tyler
    Ma, Yao
    Tang, Jiliang
    2018 IEEE INTERNATIONAL CONFERENCE ON DATA MINING (ICDM), 2018, : 929 - 934
  • [26] UNLABELED SIGNED GRAPH COLORING
    Davis, Brian
    ROCKY MOUNTAIN JOURNAL OF MATHEMATICS, 2019, 49 (04) : 1111 - 1122
  • [27] Signed Graph Attention Networks
    Huang, Junjie
    Shen, Huawei
    Hou, Liang
    Cheng, Xueqi
    ARTIFICIAL NEURAL NETWORKS AND MACHINE LEARNING - ICANN 2019: WORKSHOP AND SPECIAL SESSIONS, 2019, 11731 : 566 - 577
  • [28] Interpretable Signed Link Prediction With Signed Infomax Hyperbolic Graph
    Luo, Yadan
    Huang, Zi
    Chen, Hongxu
    Yang, Yang
    Yin, Hongzhi
    Baktashmotlagh, Mahsa
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2023, 35 (04) : 3991 - 4002
  • [29] SIGNED A-POLYNOMIALS OF GRAPHS AND POINCARE POLYNOMIALS OF REAL TORIC MANIFOLDS
    Seo, Seunghyun
    Shin, Heesung
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2015, 52 (02) : 467 - 481
  • [30] Signed Mahonian polynomials for classical Weyl groups
    Biagioli, R
    EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (02) : 207 - 217