Characterization of classes of graphs with large general position number

DOI10.1016/J.AKCEJ.2019.08.008MaRDI QIDQ4956197zbMATH OpenOpenAlexFDO

Authors Elias John Thomas, Ullas Chandran S. V.

Publication date 1 September 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

diametergeneral position numbergeneral position setgirth

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Getting inspired by the famous no-three-in-line problem and by the general position subset selection problem from discrete geometry, the same is introduced into graph theory as follows. A set $S$ of vertices in a graph $G$ is a general position set if no element of $S$ lies on a geodesic between any two other elements of $S$. The cardinality of a largest general position set is the general position number $mgp(G)$ of $G.$ In cite{ullas-2016} graphs $G$ of order $n$ with $mgp(G)$ $in2,n,n-1$ were characterized. In this paper, we characterize the classes of all connected graphs of order $ngeq4$ with the general position number $n-2.$

Recommendations

• A general position problem in graph theory
• The general position problem on Kneser graphs and on some graph operations
• Characterization of general position sets and its applications to cographs and bipartite graphs
• On general position sets in Cartesian products
• The graph theory general position problem on some interconnection networks

Cites work

• A general position problem in graph theory
• Characterization of general position sets and its applications to cographs and bipartite graphs
• Finding points in general position
• On the General Position Subset Selection Problem
• The graph theory general position problem on some interconnection networks

Cited in

(29)

• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• On the general position number of two classes of graphs
• The edge general position problem
• On the mutual visibility in Cartesian products and triangle-free graphs
• The general position achievement game played on graphs
• 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
• The graph theory general position problem on some interconnection networks
• A general position problem in graph theory
• On the general position problem on Kneser graphs
• The general position number of the Cartesian product of two trees
• General d-position sets
• On independent position sets in graphs
• Extremal edge general position sets in some graphs
• The general position avoidance game and hardness of general position games
• General position polynomials
• On the general position number of Mycielskian graphs
• On monophonic position sets in graphs
• All-path convexity: two characterizations, general position number, and one algorithm
• Variety of general position problems in graphs
• The general position number under vertex and edge removal
• Graphs whose edge general position number is 4
• Lower general position sets in graphs
• On the vertex position number of graphs
• The iteration time and the general position number in graph convexities

This page was built for publication: Characterization of classes of graphs with large general position number

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