All Questions
15 questions
1
vote
1
answer
45
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 526
1
vote
1
answer
107
views
Proving that a preorder traversal of a rooted tree $T(V, E)$ is $O(\lvert V \rvert)$ [closed]
Definition:
Let $T(V, E)$ be a rooted tree with root $r$.
If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$.
If $\lvert V \rvert > 1$, let $T_1, T_2, \...
- 19
0
votes
1
answer
354
views
Maximize sum of edge weights on spanning tree
Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$.
Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
- 11
186
votes
3
answers
96k
views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
- 343
0
votes
0
answers
123
views
Vertex cover algorithm
Given a graph $G(V, E)$, remove the vertex (or one of the vertices) with the highest cardinality from $G$ and put it in a list $L$. Repeat until in $G$ there are only vertices with cardinality $0$ (no ...
0
votes
1
answer
381
views
Maximum-weight perfect matching in a 3-regular, complete, 3-partite hypergraph
Let $H=(V, E)$ be a weighted hypergraph such that $V=A\cup B \cup C$, where $A,B,C$ are disjoint sets of size $n$, and $E=A\times B\times C$. In my particular case, $\forall e\in E$, $ wt(e)\in\{0,\pm ...
- 3
0
votes
0
answers
139
views
Reconstructing a graph from set of sequences of edges
I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...
- 283
3
votes
1
answer
178
views
A problem related to routing in a graph
I have come across a new problem - I want to know whether this problem is similar to some existing problem or not.
The new problem is this. There is a tourist who has a having the following ...
- 31
4
votes
0
answers
209
views
Rough structure of the double coset space/Graph bijections up to automorphisms
I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...
- 679
1
vote
1
answer
310
views
Counterexamples for this algorithm for recognizing lexicographic product of graphs?
Found a possible reduction from recognizing lexicographic product of graphs to 2SAT
(since 2SAT is polynomial, the algorithm is polynomial).
Can't prove completeness of the algorithm and since it is ...
- 25.4k
2
votes
1
answer
2k
views
Composite finite-state machines
A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
- 163
0
votes
0
answers
270
views
Does there exist an algorithm for computing reachability in dynamic directed forests with fast update?
I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all ...
- 163
5
votes
1
answer
362
views
Drawing graphs on circles
Please consider the following problem:
Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices.
Task: place equidistantly the vertices of $G$ on a circle of unit ...
user3409
30
votes
1
answer
3k
views
An edge partitioning problem on cubic graphs
Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
- 1,164
7
votes
1
answer
805
views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
