The graph theory general position problem on some interconnection networks

DOI10.3233/FI-2018-1748MaRDI QIDQ3120181zbMATH OpenOpenAlexWikidataFDO

Authors Paul Manuel, Sandi Klavžar

Publication date 1 March 2019

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.00244

zbMATH Keywords

Beneš networksgeneral position probleminfinite gridsinterconnection networksisometric subgraphmonotone-geodesic labeling

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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 $mgp(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"os-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 Benev{s} networks.

Recommendations

• A general position problem in graph theory
• The general position number of integer lattices
• Characterization of classes of graphs with large general position number
• The edge general position problem
• General position sets in two families of Cartesian product graphs

Cited in

(35)

• An axiomatic characterization of the position value for network situations
• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• The edge general position problem
• On the mutual visibility in Cartesian products and triangle-free graphs
• The general position achievement game played on graphs
• The general position number of Cartesian products involving a factor with small diameter
• A Steiner general position problem in graph theory
• The general position problem and strong resolving graphs
• Characterization of general position sets and its applications to cographs and bipartite graphs
• The general position number of integer lattices
• Mutual visibility in graphs
• A general position problem in graph theory
• Characterization of classes of graphs with large general position number
• On the general position problem on Kneser graphs
• On the General Position Number of Complementary Prisms
• The general position number of the Cartesian product of two trees
• General d-position sets
• General position sets in two families of Cartesian product graphs
• On the general position numbers of maximal outerplane graphs
• The general position avoidance game and hardness of general position games
• General position polynomials
• On monophonic position sets in graphs
• On the general position number of the k -th power graphs
• On the approximability of graph visibility problems
• Mobile mutual-visibility sets in graphs
• Moving through Cartesian products, coronas and joins in general position
• The general position number under vertex and edge removal
• Graphs whose edge general position number is 4
• On the vertex position number of graphs
• The iteration time and the general position number in graph convexities
• Mutual and total mutual visibility in hypercube-like graphs
• On the approximability of graph visibility problems
• The k-general d-position problem for graphs
• On the rank and the general position number in cycle convexity

This page was built for publication: The graph theory general position problem on some interconnection networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3120181)