[New query form]
887.05050
Brandstaedt, Andreas; Van Bang Le; Szymczak, Thomas
Duchet-type theorems for powers of HHD-free graphs. (English)
[J] Discrete Math. 177, No.1-3, 9-16 (1997). [ISSN 0012-365X]

The \$k\$th power of a graph \$G\$, denoted \$G\sp k\$, is the graph with the vertex set \$V(G)\$ in which two vertices are adjacent if their distance in \$G\$ is at most \$k\$. The authors prove three results of ``Duchet-type''; that is, results which read: ``If \$G\sp k\$ contains no induced subgraph of a certain type (say, long cycles), then so does \$G\sp{k+2}\$.'' They do so by employing an idea of Duchet: One can define a new graph \$(G\sp k)(X)\$, with vertices certain subsets of \$V(G)\$, that is isomorphic to \$G\sp{k+2}\$, and work out the results in \$(G\sp k)(X)\$.
[ N.F.Quimpo (Manila) ]
MSC 1991:
*05C99 Graph theory
05C38 Paths and cycles
Keywords: powers of graphs
Cited in Zbl. reviews...

[New query form]