On the Vertex Position Number of Graphs

Thankachy, Maya; Chandran, Ullas; Tuite, James; Thomas, Elias; Di Stefano, Gabriele and Erskine, Grahame (2023). On the Vertex Position Number of Graphs. Discussiones Mathematicae Graph Theory (In Press).

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 graph $G$, we say that a set $S \subseteq V(G)$ is an \emph{$x$-position set} if for any $y \in S$ the shortest $x,y$-paths in $G$ contain no point of $S\setminus \{ y\}$. 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.

Viewing alternatives

Look up in Google Scholar

Download history

Item Actions

Export

About

CORE (COnnecting REpositories)

Recommendations