General position polynomials

2024/01/11 by Vesna Iršič, Sandi Klavžar, Iršič, Vesna +5 · 6 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2401.05696

openalex publication_date 2024/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 ∑_{i ≥ 0} a_i xⁱ, 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.

Cited by

• On the Mutual Visibility of Some Moore Graphs
• General position sets in strong products with paths and cycles
• On the variety of general position problems under vertex and edge removal
• Visibility Polynomial of Some Graph Classes
• Visibility polynomial of corona of two graphs
• On the Visibility Polynomial of Graphs

Related

• The general position problem on Kneser graphs and on some graph operations
• Lower General Position Sets in Graphs
• Variety of general position problems in graphs
• The General Position Problem: A Survey
• On the General Position Number of Mycielskian Graphs