General Position Polynomials

General Position Polynomials

January 12, 2024 | Vesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite
This paper introduces the general position polynomial of a graph, which counts the number of general position sets of different sizes. A general position set is a subset of vertices where no three vertices lie on a common shortest path. The polynomial is defined as ψ(G) = ∑a_i x^i, where a_i is the number of general position sets of size i. The paper shows that the polynomial is not unimodal in general, even on trees. However, it is unimodal for certain classes of graphs, including Kneser graphs K(n,2) and some other graph operations. The general position polynomial is studied for various graph classes, including paths, cycles, complete graphs, and bipartite graphs. The paper also presents examples of graphs with non-unimodal general position polynomials and discusses the unimodality of the polynomial for specific graph families. It concludes with open problems and suggestions for future research.This paper introduces the general position polynomial of a graph, which counts the number of general position sets of different sizes. A general position set is a subset of vertices where no three vertices lie on a common shortest path. The polynomial is defined as ψ(G) = ∑a_i x^i, where a_i is the number of general position sets of size i. The paper shows that the polynomial is not unimodal in general, even on trees. However, it is unimodal for certain classes of graphs, including Kneser graphs K(n,2) and some other graph operations. The general position polynomial is studied for various graph classes, including paths, cycles, complete graphs, and bipartite graphs. The paper also presents examples of graphs with non-unimodal general position polynomials and discusses the unimodality of the polynomial for specific graph families. It concludes with open problems and suggestions for future research.
Reach us at info@study.space