Line completion number of grid graph Pn × Pm

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

References

[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.
[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. 
[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 L2(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.
Communications in Combinatorics and Optimization
Volume 6, Issue 2
December 2021
Pages 299-313

Files

Share

How to cite

Statistics