Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Vertex-Weighted Tutte Symmetric Function, and Constructing Graphs with Equal Chromatic Symmetric Function
67
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper has two main parts. First, we consider the Tutte symmetric function $XB$, a generalization of the chromatic symmetric function. We introduce a vertex-weighted version of $XB$ and show that this function admits a deletion-contraction relation. We also demonstrate that the vertex-weighted $XB$ admits spanning-tree and spanning-forest expansions generalizing those of the Tutte polynomial by connecting $XB$ to other graph functions. Second, we give several methods for constructing nonisomorphic graphs with equal chromatic and Tutte symmetric functions, and use them to provide specific examples.
rate research
Read More
This paper deals with the so-called Stanley conjecture, which asks whether they are non-isomorphic trees with the same symmetric function generalization of the chromatic polynomial. By establishing a correspondence between caterpillars trees and integer compositions, we prove that caterpillars in a large class (we call trees in this class proper) have the same symmetric chromatic function generalization of the chromatic polynomial if and only if they are isomorphic.
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.
A graph $Gamma$ is said to be symmetric if its automorphism group $rm Aut(Gamma)$ acts transitively on the arc set of $Gamma$. In this paper, we show that if $Gamma$ is a finite connected heptavalent symmetric graph with solvable stabilizer admitting a vertex-transitive non-abelian simple group $G$ of automorphisms, then either $G$ is normal in $rm Aut(Gamma)$, or $rm Aut(Gamma)$ contains a non-abelian simple normal subgroup $T$ such that $Gleq T$ and $(G,T)$ is explicitly given as one of $11$ possible exception pairs of non-abelian simple groups. Furthermore, if $G$ is regular on the vertex set of $Gamma$ then the exception pair $(G,T)$ is one of $7$ possible pairs, and if $G$ is arc-transitive then the exception pair $(G,T)=(A_{17},A_{18})$ or $(A_{35},A_{36})$.
An intuitive property of a random graph is that its subgraphs should also appear randomly distributed. We consider graphs whose subgraph densities exactly match their expected values. We call graphs with this property for all subgraphs with $k$ vertices to be $k$-symmetric. We discuss some properties and examples of such graphs. We construct 3-symmetric graphs and provide some statistics.
We discuss transpose (sometimes called universal exchange or all-to-all) on vertex symmetric networks. We provide a method to compare the efficiency of transpose schemes on two different networks with a cost function based on the number processors and wires needed to complete a given algorithm in a given time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
