On the Greedoid Tutte Polynomial for simple rooted graphs

Abstract

The Tutte polynomial, through its rank-generating formula, provides a unified framework for describing various combinatorial structures of graphs and matroids, and serves as an important polynomial invariant connecting graph theory, matroid theory, and their related applications. Let $G=(V(G),E(G),r(G))$ be a simple rooted graph, where $V(G)$ is the vertex set, $E(G)$ is the edge set, and $r(G)$ is the root. Let $\Gamma (G)$ be the greedoid induced by the rooted graph $G$, and let its greedoid Tutte polynomial be denoted by $T(\Gamma (G);x,y)$. Let $r=r(G)$, $L_r(G)=\{v\in V(G)\setminus \{r\}:rv\in E(G),d_G(v)=1\}$, and ${\ell }_r(G)=|L_r(G)|$. Gordon and McMahon proposed the following conjecture: for rooted graphs, ${\mathrm{ord}}_{x}T(\Gamma (G);x,y)={\ell }_r(G)$, where ${\mathrm{ord}}_{x}T(\Gamma (G);x,y)=\max \{a\in {\mathbb{Z}}_{\ge 0}:x^a\mid T(\Gamma (G);x,y)\}$, that is, the highest power of $x$ dividing $T(\Gamma (G);x,y)$ is equal to the number of leaf vertices adjacent to the root. In this paper, we proved that this conjecture holds for all simple rooted graphs.