Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
Gallai graphs; anti-Gallai graphs; cographs
Gallai graphs; anti-Gallai graphs; cographs
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.
References:
[1] Balakrishnan, R., Ranganathan, K.: A Text-book of Graph Theory. Springer, 1999. MR 1665381
[2] Beineke, L. W.: On derived graphs and digraphs. Beitrage zur Graphentheorie (1968), 17–23. Zbl 0179.29204
[3] Brandstädt, A., Le, V. B., Spinrad, J. P.: Graph Classes—a survey. SIAM Monographs, Philadelphia, 1999. MR 1686154
[4] Corneil, D. G., Perl, Y., Stewart, I. K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14 (1985), 926–934. DOI 10.1137/0214065 | MR 0807891
[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 10.1016/j.disc.2003.10.023 | MR 2059518
[6] Le, V. B.: Gallai and anti-Gallai graphs. Discrete Math. 159 (1996), 179–189. DOI 10.1016/0012-365X(95)00109-A | MR 1415292
[7] Mckee, T. A.: Dimensions for cographs. Ars. Comb. 56 (2000), 85–95. MR 1768604 | Zbl 0994.05127
[8] Prisner, E.: Graph Dynamics. Longman, 1995. MR 1379114 | Zbl 0848.05001
[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 2014539 | Zbl 1024.05058
[12] Sun, L.: Two classes of perfect graphs. J. Comb. Theory, Ser. B 53 (1991), 273–292. DOI 10.1016/0095-8956(91)90078-X | MR 1129555 | Zbl 0661.05055
Search
Partner of
