Questions tagged [eulerian-path]
This tag is for questions relating to Eulerian paths in graphs. An "Eulerian path" or "Eulerian trail" in a graph is a walk that uses each edge of the graph exactly once. An Eulerian path is "closed" if it starts and ends at the same vertex.
60
questions with no upvoted or accepted answers
6
votes
1
answer
206
views
Properties of prime sum graphs
The prime sum graph $P_n$ on the vertex set $V = \{1,\dots, n\}$ has an edge $e = xy$ when $x+y$ is prime. It is easy to show that any such $P_n$ is bipartite (put odd numbers in one part and evens in ...
- 1,919
3
votes
1
answer
394
views
Route Inspection Problem
The route inspection problem, is to find a shortest closed path that visits every edge of a connected undirected graph.
If $G = (V,E)$ is a tree, then any route inspection tour has $2\vert E\vert$ ...
- 51
3
votes
1
answer
561
views
Minimal edge-covering path in complete graph
Let $K_n$ be the complete graph with $n$ vertices. An edge-covering path in $K_n$ is a path going through every edge of $K_n$. The length of an edge-covering path is the number of edges (with ...
- 57
3
votes
0
answers
38
views
How is a part of eulerian path called?
An eulerian path in a graph is a path that visits every edge in the graph exactly once.
If there is a path that has a similar property that it visits an edge at most once (e.g. a part of an eulerian ...
- 241
2
votes
0
answers
107
views
When is the partition refinement graph Eulerian?
Let $n$ be a positive integer, and let $p(n)$ be the number of partitions of $n$. For two partitions $p_1, p_2$ of the same integer $n$, we say that $p_2$ is a refinement of $p_1$ if the parts of $p_1$...
- 97
2
votes
0
answers
37
views
Digraphs with exactly one Eulerian Tour
I’ve been thinking about the following problem from Richard Stanley’s list of bijective proof problems (2009). There, this problem is said to lack a combinatorial solution. The problem is the ...
- 21
2
votes
0
answers
24
views
Path / Graph problem with X nodes looking for Y paths with the most similar length.
I have the following graph / path problem:
There is exactly 1 start node and 1 end node.
There are also X (in this case 7) nodes, each connected to all other nodes and the start and end node with ...
- 131
2
votes
0
answers
211
views
Show that a graph can be separated in k disjoint trails but with at most one trail of length odd.
Let $G$ be a connected graph containing $2k$ odd vertices, where $k\ge 1$. Prove that $E(G)$ can be partitioned into subsets $E_i$, $1 \le i \le k$, where each subgraph $G[E_i]$ induced by $E_i$ is an ...
2
votes
0
answers
35
views
Graph Theory - Does a graph have an eulerian circuit if its edges can be divided into groups, each having a hamiltonian circuit?
Let $G=(V,E)$ be a graph.
Its edges can be divided into several groups such that each group has a Hamiltonian Circuit of the original graph $G$.
Does $G$ have an Eulerian Circuit?
I said yes.
If each ...
- 85
2
votes
0
answers
541
views
Maximal Eulerian subgraph in a given graph
Given a graph like the following:
how do I find the maximal Eulerian subgraph? The answer for this case should be (subgraph with blue edges):
In general, is there an algorithm to derive this ...
- 21
2
votes
0
answers
434
views
Check if graphs are Eulerian
I've been checking whether these graphs are Eulerian;
I've come to conclusion that all of them are Eulerian, because they're all connected and all the vertices are of even degree. However, when I ...
- 499
1
vote
1
answer
34
views
Worst Case Solution for directed Chinese Postman Problem
The Problem
Let $G$ be a directed graph with $n$ vertices. How long is a shortest circuit that visits every edge in the worst case? That is how long is the solution to the directed Chinese Postman ...
- 11
1
vote
0
answers
37
views
Networks: Covering each edge and starting and ending at the same vertice when repeating edges must be involved.
I'm in year 11 and my question is regarding a certain topic that I've come across in my curriculum. The problem surrounding this question is about creating a path of minimum length that covers each ...
- 11
1
vote
0
answers
55
views
Eulerian Graphs and Cycle Decompositions
I have been trying to find the following references, it would be helpful if I am linked to either of the two, both of them would be ideal.
[1] H. Fleischner, Cycle decompositions, 2-coverings, ...
1
vote
0
answers
113
views
Existence of Euler $uv$-path $\iff$ all vertices except possibly u,v are even
A statement in my course says that :
“A connected graph $G$ contains an Euler $uv$-path if and only if all vertices except possibly $u,v$ are even.”
I agree with the $\implies$ direction, but in the ...
- 1,952