The edge general position problem

DOI10.1007/S40840-022-01319-8MaRDI QIDQ2091137zbMATH OpenOpenAlexFDO

Authors R. Prabha, Sandi Klavžar, Paul Manuel

Publication date 31 October 2022

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

treehypercubepartial cubemedian graphgrid graphgeneral position problemedge general position problem

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

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 $mgp$-$set$ of $G$ and its cardinality is the $mgp$-$number$, $mgp(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, $mg{p}_e(G)$, is the size of a largest edge general position set of $G$. It is proved that $mg{p}_e(Q_r)=2^r$ and that if $T$ is a tree, then $mg{p}_e(T)$ is the number of its leaves. The value of $mg{p}_e(P_r,square,P_s)$ is determined for every $r,sge2$. To derive these results, the theory of partial cubes is used. Mulder's meta-conjecture on median graphs is also discussed along the way.

Recommendations

• Edge general position sets in Fibonacci and Lucas cubes
• General position sets in two families of Cartesian product graphs
• On general position sets in Cartesian products
• A general position problem in graph theory
• The graph theory general position problem on some interconnection networks

Cites work

• scientific article; zbMATH DE number 1339499 (Why is no real title available?)
• A general position problem in graph theory
• A note on the no-three-in-line problem on a torus
• Characterization of classes of graphs with large general position number
• Characterization of general position sets and its applications to cographs and bipartite graphs
• Classification of Vertex‐Transitive Cubic Partial Cubes
• Distance-preserving subgraphs of hypercubes
• Finding points in general position
• General \(d\)-position sets
• Handbook of product graphs
• Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
• Isometric embedding in products of complete graphs
• Media theory. Interdisciplinary applied mathematics.
• On general position sets in Cartesian products
• On no-three-in-line problem on \(m\)-dimensional torus
• On partial cubes, well-graded families and their duals with some applications in graphs
• On some properties of antipodal partial cubes
• On the Addressing Problem for Loop Switching
• On the General Position Number of Complementary Prisms
• On the General Position Subset Selection Problem
• On the extremal combinatorics of the Hamming space
• On the general position problem on Kneser graphs
• The Szeged index and the Wiener index of partial cubes with applications to chemical graphs
• The general position number of Cartesian products involving a factor with small diameter
• The general position number of integer lattices
• The general position number of the Cartesian product of two trees
• The general position problem and strong resolving graphs
• The general position problem on Kneser graphs and on some graph operations
• The graph theory general position problem on some interconnection networks
• Topological indices of the subdivision of a family of partial cubes and computation of \(\mathrm{SiO}_2\) related structures
• What do trees and hypercubes have in common?

Cited in

(10)

• A general position problem in graph theory
• General position sets in two families of Cartesian product graphs
• On the general position numbers of maximal outerplane graphs
• On the general position number of Mycielskian graphs
• The power edge set problem
• Edge general position sets in Fibonacci and Lucas cubes
• Mutual-visibility problems on graphs of diameter two
• The graph theory general position problem on some interconnection networks
• Extremal edge general position sets in some graphs
• Variety of general position problems in graphs

This page was built for publication: The edge general position problem

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