On independent position sets in graphs

• Thomas, Elias John ^[1] ; Chandran S. V., Ullas
  1. [1] Mar Ivanios College
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 40, Nº. 2, 2021, págs. 385-398
• Idioma: inglés
• DOI: 10.22199/issn.0717-6279-2021-02-0023
• Enlaces
  • Texto completo
• Resumen

  • 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

• Referencias bibliográficas
  • P. Manuel and S. Klavžar, “A general position problem in graph theory”, Bulletin of the Australian Mathematical Society, vol. 98, no. 2, pp....
  • 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...
  • M. S. Payne and D. R. Wood, “On the general position subset selection problem”, SIAM journal on discrete mathematics, vol. 27, no. 4, pp....
  • S. Ullas Chandran and G. J. Parthasarathy, “The geodesic irredundant sets in graphs”, International journal of mathematical combinatorics,...
  • B. S. Anand, S. Ullas Chandran, M. Changat, S. Klavžar, and E. J. Thomas, “Characterization of general position sets and its applications...
  • 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...
  • 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...
  • 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...