On independent position sets in graphs
Keywords:General position set, Independent set, Independent number, Independent position number
An independent set S of vertices in a graph G is an independent position set if no three vertices of S lie on a common geodesic. An independent position set of maximum size is an ip-set of G. The cardinality of an ip-set is the independent position number, denoted by ip(G). In this paper, we introduce and study the independent position number of a graph. Certain general properties of these concepts are discussed. Graphs of order n having the independent position number 1 or n − 1 are characterized. Bounds for the independent position number of Cartesian and Lexicographic product graphs are determined and the exact value for Corona product graphs are obtained. Finally, some realization results are proved to show that there is no general relationship between independent position sets and other related graph invariants
P. Manuel and S. Klavžar, “A general position problem in graph theory”, Bulletin of the Australian Mathematical Society, vol. 98, no. 2, pp. 177-187, 2018, doi: 10.1017/S0004972718000473
H. E. Dudeney, Amusements in mathematics. New York, NY: Dover, 1958.
V. Froese, I. Kanj, A. Nichterlein, and R. Niedermeier, “Finding points in general position”, International journal of computational geometry & applications, vol. 27, no. 4, pp. 277-296, 2017, doi: 10.1142/S021819591750008X
M. S. Payne and D. R. Wood, “On the general position subset selection problem”, SIAM journal on discrete mathematics, vol. 27, no. 4, pp. 1727-1733, 2013, doi: 10.1137/120897493
S. Ullas Chandran and G. J. Parthasarathy, “The geodesic irredundant sets in graphs”, International journal of mathematical combinatorics, vol. 4, 2016. [On line]. Available: https://bit.ly/3aWmKN3
B. S. Anand, S. Ullas Chandran, M. Changat, S. Klavžar, and E. J. Thomas, “Characterization of general position sets and its applications to cographs and bipartite graphs”, Applied mathematics and computation, vol. 359, pp. 84-89, 2019, doi: 10.1016/j.amc.2019.04.064
M. Ghorbani, S. Klavžar, H. R. Maimani, M. Momeni, F. Rahimi Mahid, and G. Rus, “The general position problem on kneser graphs and on some graph operations”, Mar. 2019. arXiv: 1903.04286.
B. Patkós, “On the general position problem on kneser graphs”, Mar. 2019. arXiv:1903.08056.
P. Neethu, S. Ullas Chandran, M. Changat, and S. Klavžar, “On the general position number of complementary prisms”, Jan. 2020. arXiv:2001.02189.
G. M. Thankachy, E. J. Thomas, and S. Ullas Chandran, “On the vertex position number of a graph”, unpublished.
E. J. Thomas and S. Ullas Chandran, “Characterization of classes of graphs with large general position number”, AKCE international journal of graphs and combinatorics, vol. 17, no. 3, 2020, doi: 10.1016/j.akcej.2019.08.008
R. Hammack, W. Imrich, and S. Klavžar, Handbook of product graphs, 2nd ed. Boca Raton: CRC Press, 2011, doi: 10.1201/b10959
B. S. Anand, M. Changat, U. Chandran, and P. P. Goswami, “The edge geodetic number of product graphs,” in Algorithms and discrete applied mathematics, B. S. Panda, Ed. Cham: Springer, 2018, pp. 143–154, doi: 10.1007/978-3-319-74180-2_12
How to Cite
Copyright (c) 2021 Elias John Thomas, Ullas Chandran S. V.
This work is licensed under a Creative Commons Attribution 4.0 International License.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.