Proving identities on weight polynomials of tiered trees via Tutte polynomials

DOI10.1016/J.JCTA.2022.105689zbMATH Open1498.05139arXiv2003.00625OpenAlexW3007019054MaRDI QIDQ2084993FDOQ2084993

Publication date: 14 October 2022

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

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.

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

Recommendations

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)

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)