General position polynomials

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

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.

• Jezik: Angleški jezik
• Ključne besede: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2024
• Št. strani: 16 str.
• Številčenje: Vol. 79, iss. 3, art. 110
• PID: 20.500.12556/RUL-154746
• UDK: 519.17
• ISSN pri članku: 1422-6383
• DOI: 10.1007/s00025-024-02133-3
• COBISS.SI-ID: 187024387
• Datum objave v RUL: 28.02.2024

Gradivo je del revije

• Naslov: Results in mathematics
• Skrajšan naslov: Results math.
• Založnik: Springer Nature, Birkhäuser
• ISSN: 1422-6383
• COBISS.SI-ID: 514963225

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: množice v splošni legi, število splošne lege, polinom splošne lege, unimodalnost, drevesa, kartezični produkt grafov, Kneserjevi grafi