Rank inequalities for chordal graphs (Q2366014): Difference between revisions

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).