This is my first post on MO so I hope this question is suitable. I have quite a few definitions which I will need to state before my questions at the end of this post. Please let me know if anything is unclear or if the question isn't appropriate!
Recently I was talking to a friend who works with large networks about navigating around his network. Each vertex $v$ has a "neighbourhood" $\tau (v)$ which (for the sake of this post) contains its actual neighbourhood $N(v)$ in the graph-theoretic sense as well as additional vertices which are "close" to $v$ by a similarity measure on the network. Clicking a vertex $w$ in this expanded neighbourhood of $v$ takes you to $\tau (w)$. The interesting property is that there is no need for $v$ to be in $\tau (w)$, which means that sometimes it is very hard to "get back to $v$" just by travelling from $\tau( w)$. This motivated us to make the following general definitions:
Let $G=(V(G),E(G))$ be a simple undirected graph. A function $\tau:V(G)\rightarrow \mathcal{P}(V(G))$ is a topography on $G$ if $B_1 (v)\subseteq \tau(v)$ for each vertex $v\in V(G)$, where $B_r (v)=\left\{w\in V(G):d(v,w)\leq r\right\}$. Call such a pair $(G,\tau)$ a topograph. We construct a directed graph $C_\tau (G)$ called the contour map of $(G,\tau)$ with vertex set $V(G)$ and an arc $v\to w$ iff $w\in\tau(v)$.
There are a few very simple observations to make. The fact that the neighbourhood of each vertex $v$ is contained in its "contour" $\tau (v)$ ensures that each connected component of $C_\tau (G)$ is strongly connected. A subtopograph $(H,\tau|_H )$ of $(G,\tau)$ is a subgraph $H$ of $G$ with the induced topography $\tau|_H (v) = \tau(v)\cap V(H)$. A subtopography $\sigma$ of $\tau$ is a topography such that $\sigma (v)\subseteq \tau(v)$ for each vertex $v$. Then it is not hard to see that subtopographs of $(G,\tau)$ correspond to induced subgraphs of $C_\tau (G)$ and subtopographies to spanning subgraphs. Intersection and union of topographies can be defined vertex-wise. And we can define homomorphisms of topographs $(G,\sigma)\rightarrow (H,\tau)$ as graph homomorphisms $G\rightarrow H$ which induce digraph homomorphisms $C_\sigma (G)\rightarrow C_\tau (H)$. So topographs form a category.
So a topography on a graph is a way of enlarging its neighbourhoods to connect non-adjacent vertices by some extra directed edges, chosen in a way to encode combinatorial data about the graph. The contour map then shows the relationships between the contours. Here are some examples of topographies which I've come up with:
- For $1\leq r\leq\operatorname{diam}(G)$, the map $\tau_r(v)= B_r (v)$ is a topography. For $r=1$ this gives a digraph $C_\tau^r (G)$ isomorphic to $G$ by "forgetting" the directions of the edges. For $r=\operatorname{diam}(G)$ this gives a complete digraph (arcs in both directions between all vertices). In any case this construction always makes $C_\tau (G)$ "essentially undirected" because the arcs always go both ways between vertices.
- For two distinct vertices $x,y\in V(G)$ let $\operatorname{Path}(x,y)$ be the set of all vertices on paths from $x$ to $y$ of minimal length. The $r$-betweenness topography is $$\beta_r (v) = B_1 (v)\cup\bigcup_{\substack{x\neq v\neq y \\ v\in\operatorname{Path}(x,y) \\d(x,v),d(y,v)\leq r}} \left\{x,y\right\}$$ The contour map $C_\beta^r (G)$ encodes the "betweenness" of vertices - large out-degree of a vertex (compared to in-degree) corresponds to having large betweenness. This suggests looking at a sort of "height function" $h(v) = \deg_{\operatorname{out}} (v)-\deg_{\operatorname{in}} (v)$ on the contour map. I need to look into this idea further.
- A module in a graph is a subset of vertices $M$ that are indistinguishable by vertices outside of $M$. Let $\mathcal{M}_G$ be the set of modules in a graph $G$. It is proved in lemma 23 here that the intersection of two modules is a module. Hence we define the $r$-modular topography as $$\mu_r (v)=\bigcap_{\substack{M\in\mathcal{M}_G \\ M\supseteq B_r (v)}} M$$ The contour map $C_\mu^r (G)$ is a measure of "how far from being prime" $G$ is, and is complete iff $G$ is prime. Because modules can have non-empty intersection with each other, this looks like quite an interesting case to look at more deeply.
So my questions are: firstly, has anything like this been studied before under a different name? Secondly, the topographies above are all very different, but is there anything we can say which holds for all topographies which isn't totally trivial? In this sense I am interested in both combinatorial and algebraic aspects. Finally, this is my first attempt at research so I don't have a good "sense" of what's fruitful to look at - so is there any reason to study these objects in the abstract apart form the fact that they arose fairly naturally in a discussion about network theory? Many thanks for your help!
Edit: I have just found this blog post that introduces the notion of a "directed pseudograph" as a map $G:V\rightarrow \mathcal{P}(V)$. Although it's not really relevant to any of my questions, it is interesting to note that this (along with the concept of a morphism of directed pseudographs) is exactly the original definition I came up with for a topography on a graph. I changed it to include the neighbourhood of each vertex because obviously a directed pseudograph doesn't preserve any combinatorial structure if you consider $V$ to be the vertex set of some other graph $G'$.