**
MATHEMATICA BOHEMICA, Vol. 132, No. 1, pp. 43-54 (2007)
**

#
Gallai and anti-Gallai graphs of a graph

##
Aparna Lakshmanan S., S. B. Rao, A. Vijayakumar

* Aparna Lakshmanan S.*, Department of Mathematics, Cochin University of Science and Technology, Cochin-682 022, India, e-mail: ` aparna@cusat.ac.in`; * S. B. Rao*, Stat-Math Unit, Indian Statistical Institute, Kolkata-700 108, India, e-mail: ` raosb@isical.ac.in`; * A. Vijayakumar*, Department of Mathematics, Cochin University of Science and Technology, Cochin-682 022, India, e-mail: ` vijay@cusat.ac.in`

**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.

**Keywords:** Gallai graphs, anti-Gallai graphs, cographs

**Classification (MSC2000):** 05C99

**Full text of the article:**

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]

*
© 2007–2010
FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition
*