Geodesic
Gallai and anti-Gallai graphs of a graph
Mathematica Bohemica, Tome 132 (2007) no. 1, pp. 43-54

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2007.133996
Classification : 05C15, 05C75, 05C99
Keywords: Gallai graphs; anti-Gallai graphs; cographs 
Lakshmanan S., Aparna; Rao, S. B.; Vijayakumar, A. Gallai and anti-Gallai graphs of a graph. Mathematica Bohemica, Tome 132 (2007) no. 1, pp. 43-54. doi: 10.21136/MB.2007.133996
@article{10_21136_MB_2007_133996,
     author = {Lakshmanan S., Aparna and Rao, S. B. and Vijayakumar, A.},
     title = {Gallai and {anti-Gallai} graphs of a graph},
     journal = {Mathematica Bohemica},
     pages = {43--54},
     year = {2007},
     volume = {132},
     number = {1},
     doi = {10.21136/MB.2007.133996},
     mrnumber = {2311752},
     zbl = {1174.05116},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2007.133996/}
}
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
SP  - 43
EP  - 54
VL  - 132
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2007.133996/
DO  - 10.21136/MB.2007.133996
LA  - en
ID  - 10_21136_MB_2007_133996
ER  - 
%0 Journal Article
%A Lakshmanan S., Aparna
%A Rao, S. B.
%A Vijayakumar, A.
%T Gallai and anti-Gallai graphs of a graph
%J Mathematica Bohemica
%D 2007
%P 43-54
%V 132
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2007.133996/
%R 10.21136/MB.2007.133996
%G en
%F 10_21136_MB_2007_133996

[1] Balakrishnan, R., Ranganathan, K.: A Text-book of Graph Theory. Springer, 1999. | MR

[2] Beineke, L. W.: On derived graphs and digraphs. Beitrage zur Graphentheorie (1968), 17–23. | Zbl

[3] Brandstädt, A., Le, V. B., Spinrad, J. P.: Graph Classes—a survey. SIAM Monographs, Philadelphia, 1999. | MR

[4] Corneil, D. G., Perl, Y., Stewart, I. K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14 (1985), 926–934. | DOI | MR

[5] Larrión, F., de Mello, C. P., Morgana, A., Neumann-Lara, V., Pizaña, M. A.: The clique operator on cographs and serial graphs. Discrete Math. 282 (2004), 183–191. | DOI | MR

[6] Le, V. B.: Gallai and anti-Gallai graphs. Discrete Math. 159 (1996), 179–189. | DOI | MR

[7] Mckee, T. A.: Dimensions for cographs. Ars. Comb. 56 (2000), 85–95. | MR | Zbl

[8] Prisner, E.: Graph Dynamics. Longman, 1995. | MR | Zbl

[9] Rao, S. B., Aparna Lakshmanan S., Vijayakumar, A.: Cographic and global cographic domination number of a graph, communicated.

[10] Rao, S. B., Vijayakumar, A.: Median and anti-median of a cograph, communicated.

[11] Royle, G. F.: The rank of a cograph. Electron. J. Comb. 10 (2003). | MR | Zbl

[12] Sun, L.: Two classes of perfect graphs. J. Comb. Theory, Ser. B 53 (1991), 273–292. | DOI | MR | Zbl

Cité par Sources :