General Position Polynomials

General Position Polynomials

January 12, 2024 | Vesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite
The paper introduces the general position polynomial of a graph, defined as the sum of the coefficients of distinct general position sets of the graph. A general position set is a subset of vertices where no triple of vertices lies on a common shortest path. The authors explore the properties of this polynomial for various graph classes and operations, including disjoint unions, joins, and Cartesian products. They show that the polynomial is not unimodal in general, even for trees, but it is unimodal for certain specific graph families, such as comb graphs, Kneser graphs \(K(n, 2)\), and a family of graphs containing complete bipartite graphs minus a matching. The paper also discusses the unimodality of the polynomial for specific graph operations and presents open problems and future research directions.The paper introduces the general position polynomial of a graph, defined as the sum of the coefficients of distinct general position sets of the graph. A general position set is a subset of vertices where no triple of vertices lies on a common shortest path. The authors explore the properties of this polynomial for various graph classes and operations, including disjoint unions, joins, and Cartesian products. They show that the polynomial is not unimodal in general, even for trees, but it is unimodal for certain specific graph families, such as comb graphs, Kneser graphs \(K(n, 2)\), and a family of graphs containing complete bipartite graphs minus a matching. The paper also discusses the unimodality of the polynomial for specific graph operations and presents open problems and future research directions.
Reach us at info@study.space