تخطي إلى التنقل الرئيسي تخطي إلى البحث تخطي إلى المحتوى الرئيسي

A General Position Problem in Graph Theory

  • Paul Manuel*
  • , Sandi Klavžar
  • *المؤلف المقابل لهذا العمل
  • Faculty of Mathematics and Physics
  • University of Ljubljana
  • Faculty of Natural Sciences and Mathematics
  • University of Maribor
  • Institute of Mathematics, Physics and Mechanics Ljubljana

نتاج البحث: Article › مراجعة النظراء

78 اقتباسات (Scopus)

ملخص

The paper introduces a graph theory variation of the general position problem: Given a graph , determine a largest set of vertices of such that no three vertices of lie on a common geodesic. Such a set is a max-gp-set of and its size is the gp-number of . Upper bounds on in terms of different isometric covers are given and used to determine the gp-number of several classes of graphs. Connections between general position sets and packings are investigated and used to give lower bounds on the gp-number. It is also proved that the general position problem is NP-complete.

اللغة الأصليةEnglish
الصفحات (من إلى)177-187
عدد الصفحات11
دوريةBulletin of the Australian Mathematical Society
مستوى الصوت98
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرPublished - 1 أكتوبر 2018

بصمة

أدرس بدقة موضوعات البحث “A General Position Problem in Graph Theory'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا