Clique polynomials have a unique root of smallest modulus

DOI10.1016/S0020-0190(00)00086-7MaRDI QIDQ294815zbMATH OpenWikidataFDO

Authors Massimiliano Goldwurm, Massimo Santini

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000000867?np=y

zbMATH Keywords

formal languagesrational functionsclique polynomialstrace monoids

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Formal languages and automata (68Q45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 1229629
• On a class of polynomials associated with the cliques in a graph and its applications
• Clique roots of \(K_4\)-free chordal graphs
• scientific article; zbMATH DE number 1123931
• Clique polynomials and independent set polynomials of graphs

Cites work

• scientific article; zbMATH DE number 4058887 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 1972790 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3226832 (Why is no real title available?)
• scientific article; zbMATH DE number 3346572 (Why is no real title available?)
• Combinatorial problems of commutation and rearrangements
• Determinants and Möbius functions in trace monoids
• Membership problems for regular and context-free trace languages
• Möbius functions and confluent semi-commutations
• Non-negative matrices and Markov chains. 2nd ed

Cited in

(28)

• The exact minimum number of triangles in graphs with given order and size
• Number of prefixes in trace monoids: clique polynomials and dependency graphs
• Entropy and the clique polynomial
• Deterministic concurrent systems
• Building graphs whose independence polynomials have only real roots
• On the dependence polynomial of a graph
• Synchronization of Bernoulli sequences on shared letters
• On the Minimal Density of Triangles in Graphs
• Möbius inversion formula for the trace group
• A spectral property for concurrent systems and some probabilistic applications
• Semantic equivalence of graph polynomials definable in second order logic
• Markovian dynamics of concurrent systems
• The clique density theorem
• One more remark on the adjoint polynomial
• Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
• On the roots of independence polynomials of almost all very well-covered graphs
• Introduction to Probabilistic Concurrent Systems
• A cut-invariant law of large numbers for random heaps
• On the growth of deviations
• Growth rates of geometric grid classes of permutations
• On the location of roots of graph polynomials
• A logician's view of graph polynomials
• Uniform and Bernoulli measures on the boundary of trace monoids
• On the KŁR conjecture in random graphs
• Toward uniform random generation in 1-safe Petri nets
• Note on the smallest root of the independence polynomial
• Computing the average parallelism in trace monoids.
• A new algorithm for compression of partially commutative alphabets

This page was built for publication: Clique polynomials have a unique root of smallest modulus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294815)