General d-position sets

2020/05/16 by Sandi Klavžar, Klavzar, Sandi, Douglas F. Rall +3
Computer Science · Engineering · #05C12 #05C63 #05C69 #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.2005.08095

openalex publication_date 2020/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The general d-position number \rm gp_d(G) of a graph G is the cardinality of a largest set S for which no three distinct vertices from S lie on a common geodesic of length at most d. This new graph parameter generalizes the well studied general position number. We first give some results concerning the monotonic behavior of \rm gp_d(G) with respect to the suitable values of d. We show that the decision problem concerning finding \rm gp_d(G) is NP-complete for any value of d. The value of \rm gp_d(G) when G is a path or a cycle is computed and a structural characterization of general d-position sets is shown. Moreover, we present some relationships with other topics including strong resolving graphs and dissociation sets. We finish our exposition by proving that \rm gp_d(G) is infinite whenever G is an infinite graph and d is a finite integer.

Related

• The k-general d-position problem for graphs
• Characterization of classes of graphs with large general position number
• The general position problem on Kneser graphs and on some graph operations
• The general position problem and strong resolving graph
• Characterization of general position sets and its applications to\n cographs and bipartite graphs