The Expansion of a Chord Diagram and the Tutte Polynomial
Autor: | Tomoki Nakamigawa, Tadashi Sakuma |
---|---|
Rok vydání: | 2017 |
Předmět: |
Discrete mathematics
Multiset Applied Mathematics 010102 general mathematics 0102 computer and information sciences Chord diagram 01 natural sciences Graph Theoretical Computer Science Finite sequence X.3 Combinatorics Multipartite 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Chord (music) 0101 mathematics Tutte polynomial Mathematics |
Zdroj: | Electronic Notes in Discrete Mathematics. 61:917-923 |
ISSN: | 1571-0653 |
DOI: | 10.1016/j.endm.2017.07.054 |
Popis: | A chord diagram is a set of chords of a circle such that no pair of chords has a common endvertex. A chord diagram E is called nonintersecting if E contains no crossing. For a chord diagram E having a crossing S = { x 1 x 3 , x 2 x 4 } , the expansion of E with respect to S is to replace E with E 1 = ( E ∖ S ) ∪ { x 2 x 3 , x 4 x 1 } or E 2 = ( E ∖ S ) ∪ { x 1 x 2 , x 3 x 4 } . For a chord diagram E , let f ( E ) be the chord expansion number of E , which is defined as the cardinality of the multiset of all nonintersecting chord diagrams generated from E with a finite sequence of expansions. In this paper, it is shown that the chord expansion number f ( E ) equals the value of the Tutte polynomial at the point ( 2 , − 1 ) for the interlace graph G E corresponding to E . The chord expansion number of a complete multipartite chord diagram is also studied. An extended abstract of the paper was published (Nakamigawa and Sakuma, 2017) [ 13 ]. |
Databáze: | OpenAIRE |
Externí odkaz: |