
The greedoid ``characteristic polynomial'' is studied for greedoids (anitmatroids, in this case) which arise from chordal graphs. The greedoid two-variable ``Tutte polynomial'' of Gordon and McMahon is, for a greedoid on \(E\) having rank function \(r\), \[ f(t,z) = \sum_{S \subseteq E} t^{r(E) - r(S)} z^{|A|- r(A)}. \] The greedoid ``characteristic polynomial'' is then \(p(\lambda) = (-1)^{r(G)}f(-\lambda, -1)\) (not to be confused with the one-variable ``Tutte polynomial'' \(\lambda(t) = f(0, t-1)\) of Björner, Korte, and Lovász). This paper notes that, in the case of the chordal graphs \(G\), the greedoid characteristic polynomial is given as an alternating sum \((-1)^{|E|}\sum (-1)^k a_k \lambda^k\), where \(a_k\) is the number of cliques of \(G\) having \(k\) vertices. It is shown that, for connected \(G\), the value of the ``\(\beta\) invariant'' of the greedoid, defined as \(|p^\prime(1)|\), is the number of blocks of the graph.
antimatroid, Combinatorial aspects of matroids and geometric lattices, greedoid characteristic polynomial, Beta invariant, Theoretical Computer Science, Chordal graph, Characteristic polynomial, chordal graph, Antimatroid, Greedoid, Discrete Mathematics and Combinatorics, Paths and cycles
antimatroid, Combinatorial aspects of matroids and geometric lattices, greedoid characteristic polynomial, Beta invariant, Theoretical Computer Science, Chordal graph, Characteristic polynomial, chordal graph, Antimatroid, Greedoid, Discrete Mathematics and Combinatorics, Paths and cycles
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
