Chordal graphs and the characteristic polynomial (Q1868852): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: James F. Lawrence / rank | |||
Property / reviewed by | |||
Property / reviewed by: James F. Lawrence / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(02)00500-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2164196654 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:11, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chordal graphs and the characteristic polynomial |
scientific article |
Statements
Chordal graphs and the characteristic polynomial (English)
0 references
28 April 2003
0 references
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.
0 references
chordal graph
0 references
antimatroid
0 references
greedoid characteristic polynomial
0 references