Clique polynomials have a unique root of smallest modulus

DOI10.1016/S0020-0190(00)00086-7zbMath1339.05231WikidataQ126635705 ScholiaQ126635705MaRDI QIDQ294815

Massimo Santini, Massimiliano Goldwurm

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

rational functionsformal languagesclique polynomialstrace monoids

Mathematics Subject Classification ID

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

Related Items

Introduction to Probabilistic Concurrent Systems ⋮ Building graphs whose independence polynomials have only real roots ⋮ On the dependence polynomial of a graph ⋮ The clique density theorem ⋮ One more remark on the adjoint polynomial ⋮ Markovian dynamics of concurrent systems ⋮ Toward uniform random generation in 1-safe Petri nets ⋮ A cut-invariant law of large numbers for random heaps ⋮ THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE ⋮ A new algorithm for compression of partially commutative alphabets ⋮ Computing the average parallelism in trace monoids. ⋮ On the Minimal Density of Triangles in Graphs ⋮ On the KŁR conjecture in random graphs ⋮ Growth rates of geometric grid classes of permutations ⋮ Uniform and Bernoulli measures on the boundary of trace monoids ⋮ Note on the Smallest Root of the Independence Polynomial ⋮ On the roots of independence polynomials of almost all very well-covered graphs ⋮ Möbius inversion formula for the trace group ⋮ Entropy and the clique polynomial ⋮ Synchronization of Bernoulli sequences on shared letters ⋮ Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture ⋮ A logician's view of graph polynomials ⋮ A spectral property for concurrent systems and some probabilistic applications ⋮ On the location of roots of graph polynomials ⋮ Semantic Equivalence of Graph Polynomials Definable in Second Order Logic ⋮ On the growth of deviations ⋮ Number of prefixes in trace monoids: clique polynomials and dependency graphs ⋮ Deterministic concurrent systems

Cites Work

• Möbius functions and confluent semi-commutations
• Non-negative matrices and Markov chains. 2nd ed
• Determinants and Möbius functions in trace monoids
• Membership problems for regular and context-free trace languages
• Combinatorial problems of commutation and rearrangements
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item