Your query: an = (887.05050)
Answers 1-1 (of 1)
[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]Answers 1-1 (of 1)
Zentralblatt MATH,
Copyright (c) 2000 European Mathematical Society, FIZ Karlsruhe & Springer-Verlag.