Edge general position problem

2021/05/10 by Paul Manuel, Manuel, Paul, R. Prabha +3
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2105.04292

Abstract

Given a graph G, the general position problem is to find a largest set S of vertices of G such that no three vertices of S lie on a common geodesic. Such a set is called a \rm gp-set of G and its cardinality is the \rm gp-number, \rm gp(G), of G. In this paper, the edge general position problem is introduced as the edge analogue of the general position problem. The edge general position number, \rm gp_e(G), is the size of a largest edge general position set of G. It is proved that \rm gp_e(Q_r) = 2^r and that if T is a tree, then \rm gp_e(T) is the number of its leaves. The value of \rm gp_e(P_r \square P_s) is determined for every r,s≥ 2. To derive these results, the theory of partial cubes is used. Mulder's meta-conjecture on median graphs is also discussed along the way.

Related

• Extremal edge general position sets in some graphs
• Generalization of edge general position problem
• The General Position Problem: A Survey
• The general position problem on Kneser graphs and on some graph operations
• Graph theory general position problem