Duchet-type theorems for powers of HHD-free graphs (Q1377865)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Duchet-type theorems for powers of HHD-free graphs |
scientific article |
Statements
Duchet-type theorems for powers of HHD-free graphs (English)
0 references
28 April 1998
0 references
The \(k\)th power of a graph \(G\), denoted \(G^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^k\) contains no induced subgraph of a certain type (say, long cycles), then so does \(G^{k+2}\).'' They do so by employing an idea of Duchet: One can define a new graph \((G^k)(X)\), with vertices certain subsets of \(V(G)\), that is isomorphic to \(G^{k+2}\), and work out the results in \((G^k)(X)\).
0 references
powers of graphs
0 references