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

DOI10.1016/J.AMC.2019.04.064zbMATH Open1428.05078arXiv1812.08460OpenAlexW2944343188WikidataQ127897093 ScholiaQ127897093MaRDI QIDQ2279405FDOQ2279405

Authors: Bijo S. Anand, S. V. Ullas Chandran, Manoj Changat, Sandi Klavžar, Elias John Thomas Edit this on Wikidata

Publication date: 12 December 2019

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

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.

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

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

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)

Cites Work

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

Cited In (27)

• 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
• General position polynomials
• The general position number of Cartesian products involving a factor with small diameter
• The general position problem and strong resolving graphs
• 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
• On the general position number of the k -th power graphs
• Edge general position sets in Fibonacci and Lucas cubes
• On independent position sets in graphs
• On the general position number of two classes of graphs
• General \(d\)-position sets
• On the general position number of Mycielskian graphs
• The edge general position problem
• On the mutual visibility in Cartesian products and triangle-free graphs
• On monophonic position sets in 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)