Questions tagged [network-theory]

The tag has no usage guidance.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
0 answers
61 views

Transversal deviation in first passage percolation

Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic ...
apg's user avatar
  • 612
1 vote
0 answers
45 views

Bounds on the spectral radius of a perturbed directed graph

Suppose $(G_n)$ is a sequence of strongly connected directed graphs (without multiple edges) with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be ...
a person's user avatar
1 vote
0 answers
31 views

Both-way flows in a directed graph

Let $G$ be a finite directed graph, and let $s,t$ be two distinct vertices. Problem $1(s,t)$. Find the maximum number of mutually edge-disjoint directed paths from $s$ to $t$. OK, I didn't think of ...
Brendan McKay's user avatar
1 vote
0 answers
48 views

Is a function of a centrality measure a centrality measure?

I have been trying to wrap my head around the following question. Suppose you a have a centrality measure for a weighted, undirected network. Let's call the calculated centralities with $\pmb{x}>0$....
rndm_ecn's user avatar
1 vote
0 answers
69 views

Is there a theory for forcing "sludge" through a network, analogous to electric current flows?

I'm familiar with the correspondence between reversible Markov chains, random walks, and electric current flows, as described in Probability on Trees and Networks by Lyons and Peres. Is there an ...
Syzygies's user avatar
1 vote
0 answers
255 views

total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
Ozzy's user avatar
  • 383
1 vote
0 answers
30 views

Number and different kinds of spnning trees in a weighted graph

We know that for a unweighted graph the number $\tau(\mathcal{G})$ of unique spanning trees of $\mathcal{G}$ is $$\tau(\mathcal{G})=\det L_\mathcal{G}^{\{n-1\}},$$ where $L_\mathcal{G}^{\{n-1\}}$ is ...
sleeve chen's user avatar
1 vote
0 answers
58 views

On the defect of a flow network

This problem in graph theory was actually motivated by some problems in Theory of Fractals. To formulate the problem I need to recall some definitions related to flow network. A flow network is a ...
Taras Banakh's user avatar
  • 40.8k
0 votes
0 answers
71 views

An $n$-dimensional generalized Hoffman’s circulation theorem?

For a directed graph $G$, a 1-dimensional circulation is a function $f:E(G)\rightarrow \mathbb{R}$ such that for every $v\in V(G)$, $$\sum_{uv\in E(G)}f(uv)=\sum_{vw\in E(G)}f(vw),$$ where $uv$ is an ...
Connor's user avatar
  • 251
0 votes
0 answers
40 views

Properties of preferential attachment such as spectral gap

Short question: Is there a good math reference on the properties of preferential attachment graphs? In particular, expansion properties seem to interest me. More details: I try to investigate the ...
Ron P's user avatar
  • 947
0 votes
0 answers
55 views

Does the Lawrence–Krammer representation provide a quantized action on the space of networks?

Let $\rho:B_n \rightarrow H_2(\overline{C_2 P_n})$ denote the Lawrence–Krammer representation of the braid group on $n$ symbols. The group $H_2(\overline{C_2 P_n})$ is a free $\mathbb{Z}[q,t]$-module ...
Jackson Walters's user avatar