Proving identities on weight polynomials of tiered trees via Tutte polynomials

DOI10.1016/J.JCTA.2022.105689MaRDI QIDQ2084993zbMATH OpenOpenAlexFDO

Authors Sherry H. F. Yan, F. M. Dong

Publication date 14 October 2022

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.00625

zbMATH Keywords

permutation Tutte polynomial weight function spanning tree external activity tiered graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph polynomials (05C31) Combinatorial aspects of partitions of integers (05A17)

Abstract: A {it tiered graph}

G = (V, E)

with

m

tiers is a simple graph with

, where

, and with a surjective map

t

from

V

to

such that if

v

is a vertex adjacent to

v^{'}

in

G

with

v > v^{'}

, then

t (v) > t (v^{'})

. For any ordered partition

p = (p_{1}, p_{2}, c d o t s, p_{m})

of

n

, let

s e t t_{p}

denote the set of tiered trees with vertex set

and with a map

such that

| t^{- 1} (i) | = p_{i}

for all

i = 1, 2, l d o t s, m

. For any

T i n s e t t_{p}

, let

K_{T}

denote the complete tiered graph whose vertex set and tiering map are the same as those of

T

. If the edges of

K_{T}

are ordered lexicographically by their endpoints, then the weight

w (T)

of

T

is the external activity of

T

in

K_{T}

, i.e., the number of edges

e i n E (K_{T}) s e t m i n u s E (T)

such that

e

is the least element in the unique cycle determined by

T c u p e

. Let

P_{p} (q) = s u m_{T i n s e t t_{p}} q^{w (T)}

. Dugan, Glennon, Gunnells and Steingr'imsson [J. Combin. Theory, Ser. A 164 (2019) pp. 24-49] asked for an elementary proof of the identity

P_{p} (q) = P_{p i (p)} (q)

for any permutation

p i

of

1, 2, c d o t s, m

, where

p i (p) = p_{p i (1)}, p_{p i (2)}, c d o t s, p_{p i (m)})

. In this article, we will prove an extension of this identity by applying Tutte polynomials. Furthermore, we also provide a proof of the identity

P_{(1, p_{1}, p_{2})} (q) = P_{(p_{1} + 1, p_{2} + 1)} (q)

via Tutte polynomials.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Proving identities on weight polynomials of tiered trees via Tutte polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084993)