Gallai and anti-Gallai graphs of a graph

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

Mathematica Bohemica (2007)

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

Abstract

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

How to cite

top

Lakshmanan S., Aparna, 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{LakshmananS2007,
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 = {Lakshmanan S., Aparna, 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 - Lakshmanan S., Aparna
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
  1. A Text-book of Graph Theory, Springer, 1999. (1999) MR1665381
  2. On derived graphs and digraphs, Beitrage zur Graphentheorie (1968), 17–23. (1968) Zbl0179.29204
  3. Graph Classes—a survey, SIAM Monographs, Philadelphia, 1999. (1999) MR1686154
  4. 10.1137/0214065, SIAM J. Comput. 14 (1985), 926–934. (1985) MR0807891DOI10.1137/0214065
  5. 10.1016/j.disc.2003.10.023, Discrete Math. 282 (2004), 183–191. (2004) MR2059518DOI10.1016/j.disc.2003.10.023
  6. 10.1016/0012-365X(95)00109-A, Discrete Math. 159 (1996), 179–189. (1996) MR1415292DOI10.1016/0012-365X(95)00109-A
  7. Dimensions for cographs, Ars. Comb. 56 (2000), 85–95. (2000) Zbl0994.05127MR1768604
  8. Graph Dynamics, Longman, 1995. (1995) Zbl0848.05001MR1379114
  9. Cographic and global cographic domination number of a graph, communicated, . 
  10. Median and anti-median of a cograph, communicated, . 
  11. The rank of a cograph, Electron. J. Comb. 10 (2003). (2003) Zbl1024.05058MR2014539
  12. 10.1016/0095-8956(91)90078-X, J. Comb. Theory, Ser. B 53 (1991), 273–292. (1991) Zbl0661.05055MR1129555DOI10.1016/0095-8956(91)90078-X

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.