| Title:
|
Gallai and anti-Gallai graphs of a graph (English) |
| Author:
|
Lakshmanan S., Aparna |
| Author:
|
Rao, S. B. |
| Author:
|
Vijayakumar, A. |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
132 |
| Issue:
|
1 |
| Year:
|
2007 |
| Pages:
|
43-54 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
Gallai graphs |
| Keyword:
|
anti-Gallai graphs |
| Keyword:
|
cographs |
| MSC:
|
05C15 |
| MSC:
|
05C75 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 1174.05116 |
| idMR:
|
MR2311752 |
| DOI:
|
10.21136/MB.2007.133996 |
| . |
| Date available:
|
2009-09-24T22:28:58Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133996 |
| . |
| Reference:
|
[1] Balakrishnan, R., Ranganathan, K.: A Text-book of Graph Theory.Springer, 1999. MR 1665381 |
| Reference:
|
[2] Beineke, L. W.: On derived graphs and digraphs.Beitrage zur Graphentheorie (1968), 17–23. Zbl 0179.29204 |
| Reference:
|
[3] Brandstädt, A., Le, V. B., Spinrad, J. P.: Graph Classes—a survey.SIAM Monographs, Philadelphia, 1999. MR 1686154 |
| Reference:
|
[4] Corneil, D. G., Perl, Y., Stewart, I. K.: A linear recognition algorithm for cographs.SIAM J. Comput. 14 (1985), 926–934. MR 0807891, 10.1137/0214065 |
| Reference:
|
[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. MR 2059518, 10.1016/j.disc.2003.10.023 |
| Reference:
|
[6] Le, V. B.: Gallai and anti-Gallai graphs.Discrete Math. 159 (1996), 179–189. MR 1415292, 10.1016/0012-365X(95)00109-A |
| Reference:
|
[7] Mckee, T. A.: Dimensions for cographs.Ars. Comb. 56 (2000), 85–95. Zbl 0994.05127, MR 1768604 |
| Reference:
|
[8] Prisner, E.: Graph Dynamics.Longman, 1995. Zbl 0848.05001, MR 1379114 |
| Reference:
|
[9] Rao, S. B., Aparna Lakshmanan S., Vijayakumar, A.: Cographic and global cographic domination number of a graph, communicated.. |
| Reference:
|
[10] Rao, S. B., Vijayakumar, A.: Median and anti-median of a cograph, communicated.. |
| Reference:
|
[11] Royle, G. F.: The rank of a cograph.Electron. J. Comb. 10 (2003). Zbl 1024.05058, MR 2014539 |
| Reference:
|
[12] Sun, L.: Two classes of perfect graphs.J. Comb. Theory, Ser. B 53 (1991), 273–292. Zbl 0661.05055, MR 1129555, 10.1016/0095-8956(91)90078-X |
| . |
