Characterization of general position sets and its applications to cographs and bipartite graphs

DOI10.1016/J.AMC.2019.04.064MaRDI QIDQ2279405zbMATH OpenOpenAlexWikidataFDO

Authors Bijo S. Anand, S. V. Ullas Chandran, Manoj Changat, Sandi Klavžar, Elias John Thomas

Publication date 12 December 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

bipartite complementbipartite graphcographgeneral position setgraph of diameter 2

Mathematics Subject Classification ID

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

Abstract: A vertex subset $S$ of a graph $G$ is a general position set of $G$ if no vertex of $S$ lies on a geodesic between two other vertices of $S$. The cardinality of a largest general position set of $G$ is the general position number $mgp(G)$ of $G$. It is proved that $SsubseteqV(G)$ is in general position if and only if the components of $G[S]$ are complete subgraphs, the vertices of which form an in-transitive, distance-constant partition of $S$. If $mdiam(G)=2$, then $mgp(G)$ is the maximum of $omega(G)$ and the maximum order of an induced complete multipartite subgraph of the complement of $G$. As a consequence, $mgp(G)$ of a cograph $G$ can be determined in polynomial time. If $G$ is bipartite, then $mgp(G)leqalpha(G)$ with equality if $mdiam(G)in2,3$. A formula for the general position number of the complement of an arbitrary bipartite graph is deduced and simplified for the complements of trees, of grids, and of hypercubes.

Recommendations

• The general position number of Cartesian products involving a factor with small diameter
• Characterization of classes of graphs with large general position number
• 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 Complementary Prisms

Cites work

• A family of mixed graphs with large order and diameter 2
• A general position problem in graph theory
• A note on the no-three-in-line problem on a torus
• Complement reducible graphs
• Embeddings into almost self-centered graphs of given radius
• Finding points in general position
• Handbook of product graphs
• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 2192179 (Why is no real title available?)
• Minimum edge cuts in diameter 2 graphs
• Multiplicity of eigenvalues of cographs
• No-three-in-line-in-3D
• On no-three-in-line problem on \(m\)-dimensional torus
• On the complexity of the independent set problem in triangle graphs
• On the General Position Subset Selection Problem
• On the geodetic rank of a graph
• On Wiener index of graph complements
• The chromatic symmetric functions of trivially perfect graphs and cographs
• The graph theory general position problem on some interconnection networks

Cited in

(42)

• 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
• 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
• The general position number of integer lattices
• Mutual visibility in graphs
• 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
• On independent position sets in graphs
• TRAVERSING A GRAPH IN GENERAL POSITION
• On the general position numbers of maximal outerplane graphs
• Some position problems for graphs
• Edge general position sets in Fibonacci and Lucas cubes
• 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
• Variety of general position problems in graphs
• On the general position number of the k -th power graphs
• On the approximability of graph visibility problems
• General position sets, colinear sets, and Sierpiński product graphs
• Counting largest mutual-visibility and general position sets of glued t-ary trees
• Lower general position in Cartesian products
• 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
• Mutual-visibility and general position in double graphs and in Mycielskians
• On the approximability of graph visibility problems
• Generalization of edge general position problem
• The k-general d-position problem for graphs
• On the variety of general position problems under vertex and edge removal
• Builder-blocker general position games

This page was built for publication: Characterization of general position sets and its applications to cographs and bipartite graphs

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