This paper generalizes the results of Joseph and Roby 3 on a toggle dynamical system whose state space consists of independent sets on a path graph. Along the proof, a simple generalization of the ...rotation (or circular shift) of the binary sequences arises. We show each orbit of this generalized rotation has a certain statistical symmetry.
For a tree T, consider its smallest subtree T∘ containing all vertices of degree at least 3. Then the remaining edges of T lie on edge-disjoint paths each with one endpoint on T∘. We show that the ...chromatic symmetric function of T determines the size of T∘, and the multiset of the lengths of these incident paths. In particular, this generalizes a proof of Martin, Morin, and Wagner that the chromatic symmetric function distinguishes spiders.
Many graph polynomials may be derived from the coefficients of the chromatic symmetric function X
G ${X}_{G}$ of a graph G $G$ when expressed in different bases. For instance, the chromatic ...polynomial is obtained by mapping p
n
→
x ${p}_{n}\to x$ for each n $n$ in this function, while a polynomial whose coefficients enumerate acyclic orientations is obtained by mapping e
n
→
x ${e}_{n}\to x$ for each n $n$. In this paper, we study a new polynomial we call the tree polynomial arising by mapping X
P
n
→
x ${X}_{{P}_{n}}\to x$, where X
P
n ${X}_{{P}_{n}}$ is the chromatic symmetric function of a path with n $n$ vertices. In particular, we show that this polynomial has a deletion‐contraction relation and has properties closely related to the chromatic polynomial while having coefficients that enumerate certain spanning trees and edge cutsets.
For a graph G, its Tutte symmetric function XBG generalizes both the Tutte polynomial TG and the chromatic symmetric function XG. We may also consider XB as a map from the t-extended Hopf algebra Gt ...of labeled graphs to symmetric functions.
We show that the kernel of XB is generated by vertex-relabellings and a finite set of modular relations, in the same style as a recent analogous result by Penaguião on the chromatic symmetric function X. In particular, we find one such relation that generalizes the well-known triangular modular relation of Orellana and Scott, and build upon this to give a modular relation of the Tutte symmetric function for any two-edge-connected graph that generalizes the n-cycle relation of Dahlberg and van Willigenburg. Additionally, we give a structural characterization of all local modular relations of the chromatic and Tutte symmetric functions, and prove that there is no single local modification that preserves either function on simple graphs.
PDF
