On the general position number of two classes of graphs
Yan Yao, Mengya He, Shengjin Ji
Abstract
Abstract The general position problem is to find the cardinality of the largest vertex subset <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>S</m:mi> </m:math> S such that no triple of vertices of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>S</m:mi> </m:math> S lies on a common geodesic. For a connected graph <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>G</m:mi> </m:math> G , the cardinality of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>S</m:mi> </m:math> S is denoted by <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="normal">gp</m:mi> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mi>G</m:mi> </m:mrow> <m:mo>)</m:mo> </m:mrow> </m:math> {\rm{gp}}\left(G) and called the <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="normal">gp</m:mi> </m:math> {\rm{gp}} -number (or general position number) of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>G</m:mi> </m:math> G . In the paper, we obtain an upper bound and a lower bound regarding the <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="normal">gp</m:mi> </m:math> {\rm{gp}} -number in all cacti with <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>k</m:mi> </m:math> k cycles and <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>t</m:mi> </m:math> t pendant edges. Furthermore, the exact value of the <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="normal">gp</m:mi> </m:math> {\rm{gp}} -number on wheel graphs is determined.