Document Type : Original paper

**Authors**

Christ University

**Abstract**

The concept of super line graph was introduced in the year 1995 by Bagga, Beineke and Varma. Given a graph with at least $r$ edges, the super line graph of index $r$, $L_r(G)$, has as its vertices the sets of $r$-edges of $G$, with two adjacent if there is an edge in one set adjacent to an edge in the other set. The line completion number $lc(G)$ of a graph $G$ is the least positive integer $r$ for which $L_r(G)$ is a complete graph. In this paper, we find the line completion number of grid graph $P_n \times P_m$ for various cases of $n$ and $m$.

**Keywords**

**Main Subjects**

[1] J. Bagga, Old and new generalizations of line graphs, Int. J. Math. Math. Sci. 2004 (2004), no. 29, 1509–1521.

[2] J. Bagga, L. Beineke, and B. Varma, A number theoretic problem on super line graphs, AKCE Int. J. Graphs Comb. 13 (2016), no. 2, 177–190.

[3] J. Bagga, D. Ferrero, and R. Ellis, The structure of super line graphs, 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’05), IEEE, 2005, pp. 468–471.

[4] J.S. Bagga, L.W. Beineke, and B.N. Varma, Super line graphs and their properties, in: Combinatorics, Graph Theory, Algorithms and Applications, Alavi, Y. and Lick, D. R. and Liu, J. Q., Eds., World Scientific, 1995, pp. 1–5.

[5] J.S. Bagga, L.W. Beineke, and B.N. Varma, Independence and cycles in super line graphs, Australas. J. Combin. 19

(1999), 171–178.

(1999), 171–178.

[6] J.S. Bagga, L.W. Beineke, and B.N. Varma, The super line graph L2, Discrete Math. 206 (1999), no. 1-3, 51–61.

[7] K.S. Bagga, L.W. Beineke, and B.N. Varma, The line completion number of a graph, in: Graph Theory, Combinatorics, and Applications, Alavi,Y. and Schwen, A., Eds., vol. 2, Wiley-Interscience, New York, 1995, pp. 1197–1201.

[8] K.S. Bagga, L.W. Beineke, and B.N. Varma, Super line graphs, in: Graph Theory, Combinatorics, and Applications,

Alavi,Y. and Schwen, A., Eds., vol. 1, Wiley-Interscience, New York, 1995, p. 35–46.

Alavi,Y. and Schwen, A., Eds., vol. 1, Wiley-Interscience, New York, 1995, p. 35–46.

[9] A. Gutierrez and A.S. Lladó, On the edge-residual number and the line completion number of a graph, Ars Combin. 63 (2002), 65–74.

[10] J. V. Kureethara and J. Kok, Graphs from subgraphs, in: Recent Advancements in Graph Theory, Shrimali, N. P. and Shah, N. H., Eds., CRC Press, Boca Raton, 2020, pp. 193–206.

[11] X. Li, H. Li, and H. Zhang, Path-comprehensive and vertex-pancyclic properties of super line graph L_{2}(G), Discrete Math. 308 (2008), no. 24, 6308–6315.

[12] S.A. Tapadia and B.N. Waphare, The line completion number of hypercubes, AKCE Int. J. Graphs Comb. 16 (2019), no. 1, 78–82.

December 2021

Pages 299-313