On the General Position Number of Mycielskian Graphs

MaRDI QIDQ6505606arXivFDO

Authors Elias John Thomas, Ullas Chandran, James Tuite, Gabriele Di Stefano

Published in arXiv

Mathematics Subject Classification ID

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

Abstract: The general position problem for graphs was inspired by the no-three-in-line problem and the general position subset selection problem from discrete geometry. A set $S$ of vertices of a graph $G$ is a emph{general position set} if no shortest path between two vertices of $S$ contains a third element of $S$; the general position number of $G$ is the size of a largest general position set. In this note we investigate the general position numbers of the Mycielskian of graphs, which are of interest in chromatic graph theory. We give tight upper and lower bounds on the general position number of the Mycielskian of a graph $G$ and investigate the structure of the graphs meeting these bounds. We determine this number exactly for common classes of graphs including cubic graphs and a wide range of trees.

This page was built for publication: On the General Position Number of Mycielskian Graphs

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