Rank inequalities for chordal graphs

The (chordal) graphs \(G\) discussed in this paper are finite simple graphs such that every cycle \(C\) of length at least four has an edge adjoining two nonconsecutive vertices of \(C\). The author has introduced a parameter rank \(G\) \((\text{rk}(G))\) in order to obtain generalizations of results from interval graphs to chordal graphs. Then he studies relationships between \(\text{rk}(G)\) and the extent \(e(G)\) of connected graphs \(G\), continuing a previously started program. Here \(e(G)=1+\min_ P\max_ ud(u,P)\), where \(P\) ranges over all paths of the connected graph \(G\) and \(\text{rk}(G)=\min_ Te(T)\), where \(T\) ranges over all trees such that the chordal graph \(G\) is the intersection graph of a collection of subtrees of the tree \(T\). Thus, e.g., in T.3 the author shows that if \(G\) is connected chordal, then \(e(K(G))\leq\text{rk}(G)\) for \(K(G)\) the (maximal) clique (intersection) graph of \(G\) and in T.7, \(e(G)\leq\text{rk}(G)+1\) (same hypothesis) (best possible result).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Rank inequalities for chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366014)