×

The general position problem on Kneser graphs and on some graph operations. (English) Zbl 1468.05057

Summary: A vertex subset \(S\) of a graph \(G\) is a general position set of \(G\) if no vertex of \(S\) lies on a geodesic between two other vertices of \(S\). The cardinality of a largest general position set of \(G\) is the general position number (gp-number) gp\((G)\) of \(G\). The gp-number is determined for some families of Kneser graphs, in particular for \(K(n, 2)\), \(n \geq 4\), and \(K(n, 3)\), \(n \geq 9\). A sharp lower bound on the gp-number is proved for Cartesian products of graphs. The gp-number is also determined for joins of graphs, coronas over graphs, and line graphs of complete graphs.

MSC:

05C12 Distance in graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C76 Graph operations (line graphs, products, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B.S. Anand, S.V. Ullas Chandran, M. Changat, S. Klavžar and E.J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019) 84-89. doi:10.1016/j.amc.2019.04.064 · Zbl 1428.05078
[2] G. Boruzanli Ekinci and J.B. Gauci, The super-connectivity of Kneser graphs, Discuss. Math. Graph Theory 39 (2019) 5-11. doi:10.7151/dmgt.2051 · Zbl 1401.05164
[3] B. Brešar and M. Valencia-Pabon, Independence number of products of Kneser graphs, Discrete Math. 342 (2019) 1017-1027. doi:10.1016/j.disc.2018.12.017 · Zbl 1405.05150
[4] K.N. Chadha and A.A. Kulkarni, On independent cliques and linear complementarity problems (2018). arXiv:1811.09798
[5] H.E. Dudeney, Amusements in Mathematics (Nelson, Edinburgh, 1917).
[6] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. 12 (1961) 313-320. doi:10.1093/qmath/12.1.313 · Zbl 0100.01902
[7] V. Froese, I. Kanj, A. Nichterlein and R. Niedermeier, Finding points in general position, Internat. J. Comput. Geom. Appl. 27 (2017) 277-296. doi:10.1142/S021819591750008X · Zbl 1386.68196
[8] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product (A K Peters, New York 2008). doi:10.1201/b10613 · Zbl 1156.05001
[9] M.M. Kanté, R.M. Sampaio, V.F. dos Santos and J.L. Szwarcfiter, On the geodetic rank of a graph, J. Comb. 8 (2017) 323-340. doi:10.4310/JOC.2017.v8.n2.a5 · Zbl 1367.05202
[10] S. Klavžar, B. Patkós, G. Rus and I.G. Yero, On general position sets in Cartesian grids (2019). arXiv:1907.04535v3 · Zbl 1468.05249
[11] S. Klavžar and I.G. Yero, The general position problem and strong resolving graphs, Open Math. 17 (2019) 1126-1135. doi:10.1515/math-2019-0088 · Zbl 1427.05071
[12] C.Y. Ku and K.B. Wong, On no-three-in-line problem on m-dimensional torus, Graphs Combin. 34 (2018) 355-364. doi:10.1007/s00373-018-1878-8 · Zbl 1384.05059
[13] J.H. van Lint and R.M. Wilson, A Course in Combinatorics (Cambridge University Press, Cambridge, 1992). doi:10.1017/CBO9780511987045 · Zbl 0769.05001
[14] P. Manuel and S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177-187. doi:10.1017/S0004972718000473 · Zbl 1396.05033
[15] P. Manuel and S. Klavžar, The graph theory general position problem on some interconnection networks, Fund. Inform. 163 (2018) 339-350. doi:10.3233/FI-2018-1748 · Zbl 1407.68367
[16] A. Misiak, Z. St¸epień, A. Szymaszkiewicz, L. Szymaszkiewicz and M. Zwierzchowski, A note on the no-three-in-line problem on a torus, Discrete Math. 339 (2016) 217-221. doi:10.1016/j.disc.2015.08.006 · Zbl 1322.05034
[17] T. Mütze and P. Su, Bipartite Kneser graphs are Hamiltonian, Combinatorica 37 (2017) 1207-1219. doi:10.1007/s00493-016-3434-6 · Zbl 1399.05135
[18] B. Patkós, On the general position problem on Kneser graphs (2019). arXiv:1903.08056v2 · Zbl 1464.05136
[19] M. Payne and D.R. Wood, On the general position subset selection problem, SIAM J. Discrete Math. 27 (2013) 1727-1733. doi:10.1137/120897493 · Zbl 1348.52012
[20] A. Por and D.R. Wood, No-three-in-line-in-3D, Algorithmica 47 (2007) 481-488. doi:10.1007/s00453-006-0158-9 · Zbl 1118.68106
[21] S.V. Ullas Chandran and G. Jaya Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135-143. doi:10.5281/zenodo.826834
[22] M. Valencia-Pabon and J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385. doi:10.1016/j.disc.2005.10.001 · Zbl 1100.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.