# Gallai and anti-Gallai graphs of a graph

S. Aparna Lakshmanan; S. B. Rao; A. Vijayakumar

Mathematica Bohemica (2007)

- Volume: 132, Issue: 1, page 43-54
- ISSN: 0862-7959

## Access Full Article

top## Abstract

top## How to cite

topAparna Lakshmanan, S., Rao, S. B., and Vijayakumar, A.. "Gallai and anti-Gallai graphs of a graph." Mathematica Bohemica 132.1 (2007): 43-54. <http://eudml.org/doc/250248>.

@article{AparnaLakshmanan2007,

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.},

author = {Aparna Lakshmanan, S., Rao, S. B., Vijayakumar, A.},

journal = {Mathematica Bohemica},

keywords = {Gallai graphs; anti-Gallai graphs; cographs; Gallai graphs; anti-Gallai graphs; cographs},

language = {eng},

number = {1},

pages = {43-54},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {Gallai and anti-Gallai graphs of a graph},

url = {http://eudml.org/doc/250248},

volume = {132},

year = {2007},

}

TY - JOUR

AU - Aparna Lakshmanan, S.

AU - Rao, S. B.

AU - Vijayakumar, A.

TI - Gallai and anti-Gallai graphs of a graph

JO - Mathematica Bohemica

PY - 2007

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 132

IS - 1

SP - 43

EP - 54

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

LA - eng

KW - Gallai graphs; anti-Gallai graphs; cographs; Gallai graphs; anti-Gallai graphs; cographs

UR - http://eudml.org/doc/250248

ER -

## References

top- A Text-book of Graph Theory, Springer, 1999. (1999) MR1665381
- On derived graphs and digraphs, Beitrage zur Graphentheorie (1968), 17–23. (1968) Zbl0179.29204
- Graph Classes—a survey, SIAM Monographs, Philadelphia, 1999. (1999) MR1686154
- A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985), 926–934. (1985) MR0807891
- The clique operator on cographs and serial graphs, Discrete Math. 282 (2004), 183–191. (2004) MR2059518
- Gallai and anti-Gallai graphs, Discrete Math. 159 (1996), 179–189. (1996) MR1415292
- Dimensions for cographs, Ars. Comb. 56 (2000), 85–95. (2000) Zbl0994.05127MR1768604
- Graph Dynamics, Longman, 1995. (1995) Zbl0848.05001MR1379114
- Cographic and global cographic domination number of a graph, communicated, .
- Median and anti-median of a cograph, communicated, .
- The rank of a cograph, Electron. J. Comb. 10 (2003). (2003) Zbl1024.05058MR2014539
- Two classes of perfect graphs, J. Comb. Theory, Ser. B 53 (1991), 273–292. (1991) Zbl0661.05055MR1129555

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.