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: