Affiliations: [a] Department of Information Science, College of Computing Science and Engineering, Kuwait University, Kuwait. [email protected] | [b] Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
Correspondence:
[*]
This work was supported and funded by Kuwait University, Research Project No. (QI 02/17). Address for correspondence: Department of Information Science, College of Computing Science and Engineering, Kuwait University, Kuwait.
Note: [†] Also works: Faculty of Natural Sciences and Mathematics. University of Maribor, Slovenia and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia.
Abstract: Given a graph G, the (graph theory) general position problem is to find the maximum number of vertices such that no three vertices lie on a common geodesic. This graph invariant is called the general position number (gp-number for short) of G and denoted by gp(G). In this paper, the gp-number is determined for a large class of subgraphs of the infinite grid graph and for the infinite diagonal grid. To derive these results, we introduce monotone-geodesic labeling and prove a Monotone Geodesic Lemma that is in turn developed using the Erdös-Szekeres theorem on monotone sequences. The gp-number of the 3-dim infinite grid is bounded. Using isometric path covers, the gp-number is also determined for Beneš networks.
Keywords: general position problem, monotone-geodesic labeling, interconnection networks, isometric subgraph, infinite grids, Beneš networks
