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 graphcographbipartite complementgraph of diameter 2general position set

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Minimum edge cuts in diameter 2 graphs
• Multiplicity of eigenvalues of cographs
• No-three-in-line-in-3D
• On Wiener index of graph complements
• On no-three-in-line problem on \(m\)-dimensional torus
• On the General Position Subset Selection Problem
• On the complexity of the independent set problem in triangle graphs
• On the geodetic rank of a graph
• The chromatic symmetric functions of trivially perfect graphs and cographs
• The graph theory general position problem on some interconnection networks

Cited in

(27)

• On monophonic position sets 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
• Mutual visibility in graphs
• The general position avoidance game and hardness of general position games
• A Steiner general position problem in graph theory
• Some position problems for graphs
• The general position achievement game played on graphs
• The general position number of the Cartesian product of two trees
• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• The general position number of Cartesian products involving a factor with small diameter
• The general position problem and strong resolving graphs
• General position polynomials
• Variety of general position problems in graphs
• The general position number of integer lattices
• On the general position numbers of maximal outerplane graphs
• TRAVERSING A GRAPH IN GENERAL POSITION
• Edge general position sets in Fibonacci and Lucas cubes
• On the general position number of the k -th power graphs
• On independent position sets in graphs
• On the general position number of two classes of graphs
• General \(d\)-position sets
• The edge general position problem
• On the mutual visibility in Cartesian products and triangle-free graphs
• On the general position number of Mycielskian graphs

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)