Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...
2
votes
1answer
68 views
Pairs of paths with the same source and target
Commutative diagrams usually express path equivalences in a category and thus involve pairs of paths in a category with the same source and target.
General diagrams - in categories resp. category ...
1
vote
1answer
145 views
Why the number of the vertices is even?
Let $G$ be a graph with $n$ vertices and $V$ the vertex set. Suppose that for each non-empty subset $W$ of $V$ there exists an element $\omega \in V$ ( maybe in $W$ or not) such that the degree of ...
3
votes
0answers
97 views
Diameter of subset sum graph
We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$.
Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its ...
1
vote
1answer
102 views
Probability of two vertices being connected in a random graph
Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of ...
2
votes
0answers
50 views
Usefulness of polynomial ideals for graphs
Given a graph $G=(V,E)$ on $n$ vertices, one can associate to it the polynomial $f \in k[x_1,\dots,x_n]$ given by $f = \prod_{\{i,j\}\in E}(x_i - x_j)$. Then one can map various graph properties into ...
2
votes
0answers
85 views
Maximize weighted vertex sequence subject to neighbour inclusion
Let $G=(V,E)$ be a simple undirected graph on $n$ nodes, with node weights $W = [w_1,w_2,\dots,w_n] \in \mathbb{R}^n$. Define the weight for a sequence of nodes $v_1,v_2,\dots,v_k$ by the average ...
1
vote
1answer
119 views
Endofunctors of graph categories
Let me define undirected graphs - slightly deviating from common usage - not to be a symmetric binary relation on an arbitrary finite set, but on a finite subset of $\,\mathbb{N}$. Anyway I write $G = ...
0
votes
1answer
67 views
Hitting all cycles with three disjoint vertex sets
Is the following conjecture true or false? (Hopefully it is true — I need it as a lemma.)
For every undirected graph $G=(V,E)$ there exist three pairwise disjoint sets of vertices $V_1,V_2,V_3$ ...
2
votes
2answers
71 views
Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs
From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
0
votes
0answers
39 views
clearing doubt over a definition of Zig-Zag product in graph theory [migrated]
Can anybody tell me what is a Zig-Zag product in graph theory? I am getting no idea how this product is done and how edges are defined in the product? I have some links:
...
10
votes
1answer
222 views
The number of relevant scales for a finite metric space
For an $n$-element metric space $X=\{x_1,\dots,x_n\}$ with metric
$d$ we introduce an array containing $\frac{n(n-1)}2$ numbers
$d(x_i,x_j)$, $i<j$. We assume that all distances are at least
$1$. ...
0
votes
0answers
30 views
what is a flow in the context of the ford-fulkerson algorithm? [migrated]
I am learning about the Ford Fulkerson algorithm, but having a hard time getting an intuitive feel for what a "flow" is. Is the "flow" the amount that travels between two adjacent nodes on a graph? Or ...
0
votes
0answers
24 views
vertex transitive graphs with 4p vertices with an imprimitivity block of length p and lexicographic product
Let $\Gamma$ be a vertex transitive graph with $4p$ vertices, where $p$ is an odd prime. Let $\Delta$ be an imprimitive block of length $p$ for the automorphism group of the graph. How can I prove ...
-2
votes
1answer
86 views
adjacency matrix of random geometric graphs [closed]
Consider a graph with N nodes. All nodes are distributed as a Poisson point process with density of λ in a L*L area. There is an edge between two nodes if and only if the distance between them is less ...
2
votes
1answer
135 views
Graph where non-adjacent vertices share a common neighbor?
Suppose $B$ is a bipartite graph on $n$ vertices with minimum degree $\delta$. It can be shown fairly easily that if $4 \delta >n$, we have the nice property that any two vertices in the same ...
