A survey of the studies on Gallai and anti-Gallai graphs

Document Type : Survey paper

Authors

1 Christ University, Bangalore, India

2 Department of Mathematics, GITAM University, Bangalore, India

Abstract

The Gallai graph and the anti-Gallai graph of a graph G are edge disjoint spanning subgraphs of the line graph $L(G)$. The vertices in the Gallai graph are adjacent if two of the end vertices of the corresponding edges in G coincide and the other two end vertices are nonadjacent in G. The anti-Gallai graph of G is the complement of its Gallai graph in $L(G)$. Attributed to Gallai (1967), the study of these graphs got prominence with the work of Sun (1991) and Le (1996). This is a survey of the studies conducted so far on Gallai and anti-Gallai of graphs and their associated properties.

Keywords

Main Subjects

References

[1] I. Ahmed and S. Muhmood, Computational aspects of line simplicial complexes, Journal of Intelligent & Fuzzy Systems 39, no. 8, 1–8.
[2] I. Ahmed and S. Muhmood, Characterizations of line simplicial complexes, arXiv:1702.04623 (2017).
[3] I. Ahmed and S. Muhmood, Topological and algebraic characterizations of gallai-simplicial complexes, arXiv:1701.07599 (2017).
[4] P. Anand, H. Escuadro, R. Gera, S.G. Hartke, and D. Stolee, On the hardness of recognizing triangular line graphs, Discrete Math. 312 (2012), no. 17, 2627–2638.
[5] P. Anand, H. Escuadro, R. Gera, and C. Martell, Triangular line graphs and word sense disambiguation, Discrete Appl. Math. 159 (2011), no. 11, 1160–1165.
[6] I. Anwar, Z. Kosar, and S. Nazir, An efficient algebraic criterion for shellability, arXiv:1705.09537 (2017).
[7] R. Diestel, Graph Theory, Springer, 2005.
[8] D. Dorrough, Convergence of sequences of iterated triangular line graphs, Discrete Math. 161 (1996), no. 1-3, 79–86.
[9] T. Gallai, Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica 18 (1967), no. 1-2, 25–66.
[10] P. Garg, D. Sinha, and S. Goyal, Eulerian and hamiltonian properties of gallai and anti-gallai total graphs, J. Indones. Math. Soc. 21 (2015), no. 2, 105–116.
[11] F. Harary and R.Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo 9 (1960), no. 2, 161–168.
[12] F. Joos and D. Rautenbach, Forests and trees among gallai graphs, Discrete Math. 338 (2015), no. 2, 190–195.
[13] T. Kloks, C.-H. Liu, and S.-H. Poon, On edge-independent sets, Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Springer, 2013, pp. 272–283.
[14] A. Konstantinidis, S.D. Nikolopoulos, and C. Papadopoulos, Strong triadic closure in cographs and graphs of low maximum degree, Theoret. Comput. Sci. 740 (2018), 76–84.
[15] A.L. Konstantinidis and C. Papadopoulos, Maximizing the strong triadic closure in split graphs and proper interval graphs, Discrete Appl. Math. 285 (2020), 79–95.
[16] S.A. Lakshmanan, C. Bujt´as, and Z. Tuza, Generalized line graphs: Cartesian products and complexity of recognition, Electron. J. Combin. 22 (2015), no. 3, 3–33.
[17] S.A. Lakshmanan, S.B. Rao, and A. Vijaykumar, Gallai and anti-gallai graphs
of a graph, Math. Bohem. 132 (2007), no. 1, 43–54.
[18] S.A. Lakshmanan and A. Vijayakumar, Clique irreducibility of some iterative classes of graphs, Discuss. Math. Graph Theory 28 (2008), no. 2, 307–321.
[19] S.A. Lakshmanan and A. Vijayakumar, On weakly clique irreducible graphs, (2008), Manuscript.
[20] V.B. Le, Mortality of iterated gallai graphs, Period. Math. Hungar. 27 (1993), no. 2, 105–124.
[21] V.B. Le, Gallai graphs and anti-gallai graphs, Discrete Math. 159 (1996), no. 1-3, 179–189.
[22] V.B. Le, Some conjectures on perfect graphs, Discuss. Math. Graph Theory 20 (2000), no. 1, 155–159.
[23] A. Liaquat, Characterizations of gallai total simplicial complexes, Ph.D. thesis, COMSATS University Islamabad, Lahore Campus., 2018.
[24] F. Maffray and B.A. Reed, A description of claw-free perfect graphs, J. Combin. Theory Ser. B 75 (1999), no. 1, 134–156.
[25] S. Muhmood, I. Ahmed, and A. Liaquat, Gallai simplicial complexes, Journal of Intelligent & Fuzzy Systems 36 (2019), no. 6, 5645–5651.
[26] J.J. Palathingal and S.A. Lakshmanan, Gallai and anti-gallai graph operators, Electron. Notes Discrete Math. 63 (2017), 447–453.
[27] J.J. Palathingal and S.A. Lakshmanan, Commutativity of some graph operators, Research & Reviews: Discrete Mathematical Structures 6 (2019), no. 1, 1–5.
[28] A. Poovathingal and J.V. Kureethara, Some characterizations of gallai graphs, AIP Conference Proceedings, vol. 2236, AIP Publishing LLC, 2020, p. 060003.
[29] K. Pravas and A. Vijayakumar, On an edge partition and root graphs of some classes of line graphs, Electron. J. Graph Theory Appl. 5 (2017), no. 1, 59507.
[30] L. Sun, Two classes of perfect graphs, J. Combin. Theory Ser. B 53 (1991), no. 2, 273–292.
[31] A. Vijayakumar and S.A. Lakshmanan, Clique irreducible and weakly clique irreducible graphs–a survey, India-Taiwan Conference on Discrete Mathematics, p. 114.
[32] W.D. Wallis and G.-H. Zhang, On maximal clique irreducible graphs, J. Combin. Math. Combin. Comput 8 (1990), 187–193.
[33] T.-M. Wang, On characterizing weakly maximal clique irreducible graphs, Congr. Numer. (2003), 177–188.
 
Communications in Combinatorics and Optimization
Volume 6, Issue 1
June 2021
Pages 93-112

Files

Share

How to cite

Statistics