2022/01/29 by Xiaxia Guan, Guan, Xiaxia, Xian’an Jin +1
Engineering · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2201.12531
openalex publication_date 2022/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The interior polynomial and the exterior polynomial are generalizations of valuations on (1/ξ,1) and (1,1/η) of the Tutte polynomial TG(x,y) of graphs to hypergraphs, respectively. The pair of hypergraphs induced by a connected bipartite graph are abstract duals and are proved to have the same interior polynomial, but may have different exterior polynomials. The top of the HOMFLY polynomial of a special alternating link coincides with the interior polynomial of the pair of hypergraphs induced by the Seifert graph of the link. Let G=(V∪ E, ε) be a connected bipartite graph. In this paper, we mainly study the coefficients of the interior and exterior polynomials. We prove that the interior polynomial of a connected bipartite graph is interpolating. We strengthen the known result on the degree of the interior polynomial for connected bipartite graphs with 2-vertex cuts in V or E. We prove that interior polynomials for a family of balanced bipartite graphs are monic and the interior polynomial of any connected bipartite graph can be written as a linear combination of interior polynomials of connected balanced bipartite graphs. The exterior polynomial of a hypergraph is also proved to be interpolating. It is known that the coefficient of the linear term of the interior polynomial is the nullity of the bipartite graph, we obtain a `dual' result on the coefficient of the linear term of the exterior polynomial: if G-e is connected for each e∈ E, then the coefficient of the linear term of the exterior polynomial is |V|-1. Interior and exterior polynomials for some families of bipartite graphs are computed.