Chordal graphs and the characteristic polynomial
type: Item
instance of: scholarly article
title: Chordal graphs and the characteristic polynomial
zbMATH Open document ID: 1017.05059
DOI: 10.1016/S0012-365X(02)00500-9
author: Elizabeth McMahon
author: Beth A. Shimkus
author: Jessica A. Wolfson
published in: Discrete Mathematics
publication date: 2003-04-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 1901901
zbMATH Keywords: chordal graph
zbMATH Keywords: antimatroid
zbMATH Keywords: greedoid characteristic polynomial
reviewed by: James F. Lawrence
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00500-9
OpenAlex ID: W2164196654
Recommended article: On chordal graphs and their chromatic polynomials
Recommended article: Q3822188
Recommended article: Q4517020
Recommended article: Q4033253
Recommended article: The Neighborhood Polynomial of Chordal Graphs
Recommended article: The neighborhood polynomial of chordal graphs
Recommended article: Chordal characterization of graphic matroids
Recommended article: Graphs determined by their generalized characteristic polynomials
Recommended article: A generalization of chordal graphs
Recommended article: On the chordality of a graph
description: scientific article; zbMATH DE number 1901901