On independent position sets in graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-2021-02-0023Keywords:
General position set, Independent set, Independent number, Independent position numberAbstract
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
References
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
Published
How to Cite
Issue
Section
Copyright (c) 2021 Elias John Thomas, Ullas Chandran S. V.
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
