Title of article :
Tree width and regular triangulations
Author/Authors :
Andrei Kotlov، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2001
Pages :
5
From page :
187
To page :
191
Abstract :
Consider the regular triangulation of an equilateral triangle into (k−1)2 congruent triangles. Define the graph Δk as the skeleton of this triangulation. Recently, using spectral methods, Colin de Verdière showed that the tree width of Δk is k. In this note, we show that Δk is, in fact, a forbidden minor for the property of having tree width less than k. As a corollary, we derive a similar result for a spectral graph invariant.
Keywords :
Colin de Verdiere number , Forbidden minor , Tree width
Journal title :
Discrete Mathematics
Serial Year :
2001
Journal title :
Discrete Mathematics
Record number :
949761
Link To Document :
بازگشت