Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA tree distinguishing polynomial
76
0
0.0
(
0
)
Authors
Pengyu Liu
Ask ChatGPT about the research
No Arabic abstract
We define a bivariate polynomial for unlabeled rooted trees and show that the polynomial of an unlabeled rooted tree $T$ is the generating function of a class of subtrees of $T$. We prove that the polynomial is a complete isomorphism invariant for unlabeled rooted trees. Then, we generalize the polynomial to unlabeled unrooted trees and we show that the generalized polynomial is a complete isomorphism invariant for unlabeled unrooted trees.
rate research
Read More
In this paper, we propose an algebraic approach to determine whether two non-isomorphic caterpillar trees can have the same symmetric function generalization of the chromatic polynomial. On the set of all composition on integers, we introduce: An operation, which we call composition product; and a combinatorial polynomial, which we call the composition-lattice polynomial or L-polynomial, that mimics the weighted graph polynomial of Noble and Welsh. We prove a unique irreducible factorization theorem and establish a connection between the L-polynomial of a composition and its irreducible factorization, namely that reversing irreducible factors does not change L, and conjecture that is the only way of generating such compositions. Finally, we find a sufficient condition for two caterpillars have a different symmetric function generalization of the chromatic polynomial, and use this condition to show that if our conjecture were to hold, then the symmetric function generalization of the chromatic polynomial distinguishes among a large class of caterpillars.
We study emph{edge-sum distinguishing labeling}, a type of labeling recently introduced by Tuza in [Zs. Tuza, textit{Electronic Notes in Discrete Mathematics} 60, (2017), 61-68] in context of labeling games. An emph{ESD labeling} of an $n$-vertex graph $G$ is an injective mapping of integers $1$ to $l$ to its vertices such that for every edge, the sum of the integers on its endpoints is unique. If $l$ equals to $n$, we speak about a emph{canonical ESD labeling}. We focus primarily on structural properties of this labeling and show for several classes of graphs if they have or do not have a canonical ESD labeling. As an application we show some implications of these results for games based on ESD labeling. We also observe that ESD labeling is closely connected to the well-known notion of emph{magic} and emph{antimagic} labelings, to the emph{Sidon sequences} and to emph{harmonious labelings}.
A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such coloring. The distinguishing threshold of $G$, denoted by $theta(G)$, is the minimum number $k$ such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $theta(G)$, find its relation to the cycle structure of the automorphism group of $G$ and prove that $theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $overline{K_n}$. Finally, we consider the graphs in the Johnson scheme for their distinguishing numbers and thresholds.
Following Britz, Johnsen, Mayhew and Shiromoto, we consider demi-ma-troids as a(nother) natural generalization of matroids. As they have shown, demi-ma-troids are the appropriate combinatorial objects for studying Weis duality. Our results here apport further evidence about the trueness of that observation. We define the Hamming polynomial of a demimatroid $M$, denoted by $W(x,y,t)$, as a generalization of the extended Hamming weight enumerator of a matroid. The polynomial $W(x,y,t)$ is a specialization of the Tutte polynomial of $M$, and actually is equivalent to it. Guided by work of Johnsen, Roksvold and Verdure for matroids, we prove that Betti numbers of a demimatroid and its elongations determine the Hamming polynomial. Our results may be applied to simplicial complexes since in a canonical way they can be viewed as demimatroids. Furthermore, following work of Brylawski and Gordon, we show how demimatroids may be generalized one step further, to combinatroids. A combinatroid, or Brylawski structure, is an integer valued function $rho$, defined over the power set of a finite ground set, satisfying the only condition $rho(emptyset)=0$. Even in this extreme generality, we will show that many concepts and invariants in coding theory can be carried on directly to combinatroids, say, Tutte polynomial, characteristic polynomial, MacWilliams identity, extended Hamming polynomial, and the $r$-th generalized Hamming polynomial; this last one, at least conjecturelly, guided by the work of Jurrius and Pellikaan for linear codes. All this largely extends the notions of deletion, contraction, duality and codes to non-matroidal structures.
We extend the Penrose polynomial, originally defined only for plane graphs, to graphs embedded in arbitrary surfaces. Considering this Penrose polynomial of embedded graphs leads to new identities and relations for the Penrose polynomial which can not be realized within the class of plane graphs. In particular, by exploiting connections with the transition polynomial and the ribbon group action, we find a deletion-contraction-type relation for the Penrose polynomial. We relate the Penrose polynomial of an orientable checkerboard colourable graph to the circuit partition polynomial of its medial graph and use this to find new combinatorial interpretations of the Penrose polynomial. We also show that the Penrose polynomial of a plane graph G can be expressed as a sum of chromatic polynomials of twisted duals of G. This allows us to obtain a new reformulation of the Four Colour Theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
