All Questions
9 questions
5
votes
1
answer
171
views
Graph combinatorial optimization problem
Let $G$ be a simple graph with vertex set $V$, such that for any two vertices $u,v\in V$, we have at least $k$ edge-disjoint paths of length $2$ (i.e., formed by $2$ edges) connecting $u$ with $v$. ...
- 1,677
1
vote
1
answer
165
views
Combinatorial graph optimization problem on integer adjacency matrices
We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers.
Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and
$z:=\...
- 1,677
2
votes
1
answer
155
views
Combinatorial process on multisets of integers
Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments:
We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
- 1,677
8
votes
1
answer
391
views
Sum of degree differences for simple graphs
For a simple graph $G$ on $n$ vertices, let us define
$$\mathcal{I}_{n}(G)=\sum_{i,j=1}^{n}|\deg\ x_{i}-\deg\ x_{j}|^{3}.$$
I know that there are many different topological indices defined and ...
user153000
2
votes
0
answers
108
views
What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph
By a classical theorem of Nash-Williams, the edges of every connected $n$-vertex planar graph can be covered by three trees $T_1,T_2$ and $T_3$. Does anyone know of any results from an article or a ...
- 1,190
3
votes
1
answer
305
views
Counting the forests obtainable by removing subtrees from binary trees
Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).
For any ...
- 1,677
2
votes
1
answer
164
views
Combinatorial optimization for a sequential random process on graphs
Let $G(V, E)$ be a simple graph with $|V|=n$, and let $h$ be an integer in $[n]$.
We repeat $h$-many times the following operation in a sequential fashion, where the graph may change at each round. ...
- 1,677
3
votes
1
answer
179
views
Reference Request: designing a tree of "main roads" in a graph
Let $G = (V, E)$ be an undirected finite connected graph. Let $u$ be a specified vertex of $G$. Then the sum of distances
$$
\sum_{v \in V} d_G(u,v)
$$
is defined. Now we want to decrease this value, ...
- 1,551
2
votes
0
answers
44
views
Estimates for the drop in the sum of all pairwise weighted distances effected by a decrease of the weight of an edge
Consider simple connected undirected graphs $G = (V, E)$ equipped with a function $w\colon E\rightarrow \{x\in \mathbb{R}\colon x\geq 0\}$.
Define a function $d_{G,w}\colon V\times V\rightarrow\...
- 1,551