On the Vertex Position Number of Graphs

arXiv2209.00359MaRDI QIDQ6409449FDOQ6409449

Authors: Maya G. S. Thankachy, Elias John Thomas, Ullas Chandran, James Tuite, Gabriele Di Stefano, Grahame Erskine 

Publication date: 1 September 2022

Abstract: In this paper we generalise the notion of visibility from a point in an integer lattice to the setting of graph theory. For a vertex $x$ of a connected graph $G$, we say that a set $SsubseteqV(G)$ is an emph{$x$-position set} if for any $yinS$ the shortest $x,y$-paths in $G$ contain no point of $Ssetminusy$. We investigate the largest and smallest orders of maximum $x$-position sets in graphs, determining these numbers for common classes of graphs and giving bounds in terms of the girth, vertex degrees, diameter and radius. Finally we discuss the complexity of finding maximum vertex position sets in graphs.

Mathematics Subject Classification ID

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

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

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