7
$\begingroup$

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:

  1. 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.
  2. 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.
  3. 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'$.

$\endgroup$
  • 1
    $\begingroup$ The information content of a topography appears to be that of an undirected graph together with some additional directed edges. It's not clear to me that there is anything else that can be said about these objects in this generality. (In case it's useful, your first example is called taking powers of a graph.) $\endgroup$ – Ben Barber Mar 30 '15 at 11:25
  • 1
    $\begingroup$ @BenBarber thanks for the reference to graph powers - I'm glad one of these things has a name, and it has some nice properties too. I now think that the setup is too general, and I will maybe concentrate on a specific topography (maybe my modular one) and see if anything interesting comes from it. $\endgroup$ – Alex Saad Mar 30 '15 at 13:14
  • $\begingroup$ It may be worth noting that the term "topograph" already has at least one mathematical use, which differs from the one above: John Conway uses it for a certain graph related to integral quadratic forms. See e.g. here -- this is the second blog post in a series of 3 about these things; I linked to the second rather than the first because it has some pictures :-). $\endgroup$ – Gareth McCaughan Jan 30 '18 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.