The graph theory general position problem on some interconnection\n networks

2017/09/30 by Paul Manuel, Manuel, Paul, Sandi Klavžar +1 · 2 citations
Computer Science · #05C12 #05C82 #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1710.00244

openalex publication_date 2017/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a graph G, the (graph theory) general position problem is to find the\nmaximum number of vertices such that no three vertices lie on a common\ngeodesic. This graph invariant is called the general position number (gp-number\nfor short) of G and denoted by rm gp(G). In this paper, the gp-number is\ndetermined for a large class of subgraphs of the infinite grid graph and for\nthe infinite diagonal grid. To derive these results, we introduce\nmonotone-geodesic labeling and prove a Monotone Geodesic Lemma that is in turn\ndeveloped using the Erd "os-Szekeres theorem on monotone sequences. The\ngp-number of the 3-dim infinite grid is bounded. Using isometric path covers,\nthe gp-number is also determined for Bene vs networks.\n

Cited by

• Fault-tolerant mutual-visibility: complexity and solutions for grid-like networks
• General position sets in strong products with paths and cycles

Related

• General d-position sets
• The k-general d-position problem for graphs
• Generalization of edge general position problem
• Characterization of classes of graphs with large general position number
• The general position number of integer lattices