The cyclomatic number of a graph and its independence polynomial at \(- 1\)
From MaRDI portal
Publication:1950412
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
cyclomatic numbermaximum independent setindependence polynomialdecycling numbernumber of independent setsunicyclic well-covered graphwell-covered trees
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