General position polynomials

Iršič, Vesna (author), Klavžar, Sandi (author), Rus, Gregor (author), Tuite, James (author)

A subset of vertices of a graph $G$ is a general position set if no triple of vertices from the set lie on a common shortest path in $G$. In this paper we introduce the general position polynomial as $\sum_{i \geq 0} a_i x^i$, where $a_i$ is the number of distinct general position sets of $G$ with cardinality $i$. The polynomial is considered for several well-known classes of graphs and graph operations. It is shown that the polynomial is not unimodal in general, not even on trees. On the other hand, several classes of graphs, including Kneser graphs $K(n,2)$, with unimodal general position polynomials are presented.

• Language: English
• Keywords: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2024
• Number of pages: 16 str.
• Numbering: Vol. 79, iss. 3, art. 110
• PID: 20.500.12556/RUL-154746
• UDC: 519.17
• ISSN on article: 1422-6383
• DOI: 10.1007/s00025-024-02133-3
• COBISS.SI-ID: 187024387
• Publication date in RUL: 28.02.2024

Record is a part of a journal

• Title: Results in mathematics
• Shortened title: Results math.
• Publisher: Springer Nature, Birkhäuser
• ISSN: 1422-6383
• COBISS.SI-ID: 514963225

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: množice v splošni legi, število splošne lege, polinom splošne lege, unimodalnost, drevesa, kartezični produkt grafov, Kneserjevi grafi