Roots of graph polynomials such as the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others are widely studied. In this paper we examine to what extent the ...location of these roots reflects the graph theoretic properties of the underlying graph.
There exists a variety of coloring problems for plane graphs, involving vertices, edges, and faces in all possible combinations. For instance, in the entire coloring of a plane graph we are to color ...these three sets so that any pair of adjacent or incident elements get different colors. We study here some problems of this type from algebraic perspective, focusing on the facial variant. We obtain several results concerning the Alon–Tarsi number of various graphs derived from plane embeddings. This allows for extensions of some previous results for choosability of these graphs to the game theoretic variant, known as paintability. For instance, we prove that every plane graph is facially entirely 8-paintable, which means (metaphorically) that even a color-blind person can facially color the entire graph from lists of size 8.
We introduce a generalization of the Krushkal polynomial to nonorientable surfaces, and prove that this polynomial has a natural quasi-tree expansion. This generalized Krushkal polynomial contains ...the Bollobás–Riordan polynomial of a (possibly nonorientable) ribbon graph as a specialization. The quasi-tree expansion proven here then extends the recent quasi-tree expansions of the Bollobás–Riordan polynomial deduced in the oriented case by A. Champanerkar et al. and in the more general unoriented case by E. Dewey and F. Vignes-Tourneret. The generalized Krushkal polynomial also contains the Las Vergnas polynomial of a cellulation of a surface as a specialization; we use this fact to deduce a quasi-tree expansion for the Las Vergnas polynomial.
The Wiener polynomial of a connected graph G is the polynomial W(G;x)=∑i=1D(G)di(G)xi where D(G) is the diameter of G, and di(G) is the number of pairs of vertices of G at distance i from each other. ...We examine the roots of Wiener polynomials of trees. We prove that the collection of real Wiener roots of trees is dense in (−∞,0, and the collection of complex Wiener roots of trees is dense in ℂ. We also prove that the maximum modulus among all Wiener roots of trees of order n≥31 is between 2n−16 and 2n−15, and we determine the unique tree that achieves the maximum for n≥31. Finally, we find trees of arbitrarily large diameter whose Wiener roots are all real.
On the roots of Wiener polynomials of graphs Brown, Jason I.; Mol, Lucas; Oellermann, Ortrud R.
Discrete mathematics,
September 2018, 2018-09-00, Letnik:
341, Številka:
9
Journal Article
Recenzirano
Odprti dostop
The Wiener polynomial of a connected graph G is defined as W(G;x)=∑xd(u,v), where d(u,v) denotes the distance between u and v, and the sum is taken over all unordered pairs of distinct vertices of G. ...We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order n is n2−1, the maximum modulus among all roots of Wiener polynomials of trees of order n grows linearly in n. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely (−∞,0, while in the case of trees, it contains (−∞,−1. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.
Let $ G $ be a graph. A dissociation set of $ G $ is a subset of vertices that induces a subgraph with vertex degree at most 1. The dissociation polynomial of $ G $ is $ D_{G}(\lambda) = \sum_{D \in ...\mathcal{D}(G)} \lambda^{|D|} $, where $ \mathcal{D}(G) $ is the set of all dissociation sets of $ G $. In this paper, we prove that for any cubic graph $ G $ and any $ \lambda \in(0, 1 $,
<disp-formula> <tex-math id="FE1"> \begin{document}$ \frac{1}{|V(G)|} \ln D_{G}(\lambda) \leq \frac{1}{4} \ln D_{K_4}(\lambda) $\end{document} </tex-math></disp-formula>
with equality if and only if $ G $ is a disjoint union of copies of the complete graph $ K_{4} $. When $ \lambda = 1 $, the value of $ D_G(\lambda) $ is exactly the number of dissociation sets of $ G $. Hence, for any cubic graph $ G $ on $ n $ vertices, $ |\mathcal{D}(G)|\leq|\mathcal{D}(K_4)|^{n/4} = 11^{n/4}. $
In theoretical chemistry, topological indices are commonly employed to model the physico-chemical properties of chemical compounds. Mathematicians frequently use Zagreb indices to calculate a ...chemical compound's strain energy, melting point, boiling temperature, distortion, and stability. The current global pandemic caused by the new SARS-CoV-2, also known as COVID-19, is a significant public health concern. Various therapy modalities are advised. The issue has become worse since there hasn't been enough counseling. Researchers are looking at compounds that might be used as SARS and MERS therapies based on earlier studies. In several quantitative structure-property-activity relationships (QSPR and QSAR) studies, a variety of physiochemical properties are successfully represented by topological indices, a sort of molecular descriptor that just specifies numerical values connected to a substance's molecular structure. This study investigates several irregularity-based topological indices for various antiviral medicines, depending on the degree of irregularity. In order to evaluate the effectiveness of the generated topological indices, a QSPR was also carried out using the indicated pharmaceuticals, the various topological indices, and the various physiochemical features of these antiviral medicines. The acquired results show a substantial association between the topological indices being studied by the curve-fitting approach and the physiochemical properties of possible antiviral medicines.
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious ...colorings, convex colorings, mcct-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial χ(G;X) is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcct-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results.
This paper focuses on the well-known problem due to Stanley of whether two non-isomorphic trees can have the same U-polynomial (or, equivalently, the same chromatic symmetric function). We consider ...the Uk-polynomial, which is a restricted version of U-polynomial, and construct, for any given k, non-isomorphic trees with the same Uk-polynomial. These trees are constructed by encoding solutions of the Prouhet–Tarry–Escott problem. As a consequence, we find a new class of trees that are distinguished by the U-polynomial up to isomorphism.
PDF
