All Questions
8 questions with no upvoted or accepted answers
7
votes
0
answers
74
views
Graphs all of whose cuts are positive
Let $(V, E, w)$ a weighted graph, with vertices $V$, edges $E$, and signed weight $w:E\to \mathbb R$.
I am interested to know other popular properties that are known to imply, or are equivalent to, ...
- 2,041
3
votes
0
answers
346
views
Terminology for transforming a directed acyclic graph into a tree
I am looking for the term of converting a directed acyclic graph (DAG) into a tree by traversing its topologically ordered nodes and copying the subtrees of the nodes with in-degree $> 1$.
Such a ...
- 265
2
votes
0
answers
124
views
Graphs which are built from complete graphs : Reference request
Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$.
We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...
- 1,269
1
vote
0
answers
72
views
Another betweenness centrality measure: neighbourhood centrality
Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind).
Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node ...
- 9,720
1
vote
0
answers
35
views
Term or reference for a set of integer edge weights to guarantee distinct weighted degrees
I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...
- 11
1
vote
0
answers
337
views
What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?
Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph?
Update ...
- 1,826
0
votes
0
answers
102
views
Merging two composable walks in a graph
Let $G$ be a graph (i.e., an undirected graph in which we allow for loops and parallel edges). Denote by $V$ the vertex set, by $E$ the edge set, and by $\psi$ the incidence function of $G$, and let $\...
- 10.5k
0
votes
0
answers
307
views
Graph Coloring: Two adjacent vertices share same color
Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices.
Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$.
The edge set ...
- 267