GALLAI AND ANTI-GALLAI GRAPHS OF A GRAPH
| Data(s) |
04/02/2010
04/02/2010
04/02/2010
|
|---|---|
| Resumo |
Abstract. The paper deals with graph operators-the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H-free for any finite graph H. The case of complement reducible graphs-cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained. |
| Identificador | |
| Idioma(s) |
en |
| Palavras-Chave | #Keywords: Gallai graphs, anti-Gallai graphs, #cographs |
| Tipo |
Working Paper |
