The cyclomatic number of a graph and its independence polynomial at \(- 1\)

DOI10.1007/s00373-011-1101-7zbMath1266.05071arXiv0904.4819MaRDI QIDQ1950412

Vadim E. Levit, Eugen Mandrescu

Publication date: 13 May 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.4819

zbMATH Keywords

cyclomatic numbermaximum independent setindependence polynomialdecycling numbernumber of independent setsunicyclic well-covered graphwell-covered trees

Mathematics Subject Classification ID

05C31: Graph polynomials

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Graph polynomials for a class of DI-pathological graphs, The domination polynomial of a graph at \(-1\), A bound on the values of independence polynomials at \(-1/k\) for \(k\)-degenerate graphs, Extremal problems related to Betti numbers of flag complexes, Graphs whose certain polynomials have few distinct roots, Domination polynomials of \(k\)-tree related graphs, A simple proof of an inequality connecting the alternating number of independent sets and the decycling number, Upper bounds for the independence polynomial of graphs at \(-1\), On roots of Wiener polynomials of trees, A note on the values of independence polynomials at \(-1\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple proof of an inequality connecting the alternating number of independent sets and the decycling number
• On the independence complex of square grids
• Upper bounds on the Witten index for supersymmetric lattice models by discrete Morse theory
• Algebraic properties of edge ideals via combinatorial topology
• Complexes of directed trees and independence complexes
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• A characterization of well covered graphs of girth 5 or greater
• Clique polynomials and independent set polynomials of graphs
• Roots of independence polynomials of well covered graphs
• Very well covered graphs
• The interlace polynomial of graphs at \(-1\)
• Graphs, partitions and Fibonacci numbers
• Simplicial complexes of graphs
• Independence complexes of claw-free graphs
• On the roots of independence polynomials of almost all very well-covered graphs
• Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
• The number of independent sets in unicyclic graphs
• Decycling graphs
• Some covering concepts in graphs