Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

4
votes
1answer
91 views
+50

Where can I learn more about the Galois connection induced by a graph on its own powerset?

Given a binary relation $R \subseteq X \times Y$, we get an antitone Galois connection $(F,U) : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ in the usual way: The function $U : \mathcal{P}(X) ...
1
vote
1answer
60 views
+50

counting occurence of subgraphs by counting their occurence in larger subgraphs

I have a mental block in fully understanding the following notion. Let $G$ be a graph of order $n$ and $H$ a fixed small graph of order $k \le n$. Suppose that there are $d$ copies of $H$ as an ...
4
votes
1answer
66 views
+500

How many directed graphs of size n are there where each vertex is the tail of exactly one edge?

In a research problem in an unrelated area, me and a student found it necessary to count the number of directed graphs with every vertex having one outward-pointing edge, with no restrictions on the ...