All Questions
Tagged with eulerian-path hamiltonian-path
46
questions
-1
votes
1
answer
43
views
What are necessary and sufficient conditions to have a negative cycle in a directed graph with some negative edges? [closed]
Trying to test Johnson’s algorithm with over 100 vertices but it doesn’t work if there is a negative cycle. So I’m trying to write code to construct graphs with some negative weights (about 10% of the ...
- 35
0
votes
1
answer
104
views
Finding path lengths by the power of adjacency matrix of an undirected graph
The same question was asked almost 7 years ago. It turned out to be a matter of terminology in different textbooks between the terms "path" and "walk". While the answers addressed ...
- 103
0
votes
1
answer
774
views
Graph problem about roads built between towns [closed]
There are 10 cities in a country. The Government starts to build direct roads between the cities, but with random access, it can build direct road between two cities even if there is already another ...
- 21
2
votes
1
answer
150
views
Every bipartite Eulerian graph is a Hamilton graph
This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer and help me prove it?
What I think: false, but I can not come up with an example.
- 115
0
votes
1
answer
63
views
Are all 4-regular Hamiltonian graphs Euler graphs?
This is a true/false question I'm trying to solve to prepare for my exam.
Could someone confirm my answer?
What I think:
true, because the graph then has only even degrees and the graph is also ...
- 115
0
votes
0
answers
56
views
Is it possible to arrange handshakes in this way?
I am reading Eulerian graphs from this pdf. In page 210, exercise 9.5.7, I am stuck at following problem.
Each of 8 persons in a room has to hand shake with every other person as per the following ...
- 5,409
2
votes
3
answers
312
views
Does the graph contain a Hamiltonian and an Euler cycle?
Question:
Let $G=(V_n,E_n)$ such that:
G's vertices are words over $\sigma=\{a,b,c,d\}$ with length of $n$, such that there aren't two adjacent equal chars.
An edge is defined to be between two ...
- 882
1
vote
1
answer
269
views
Characterizing graphs for which the subdivision graph S(G) is Eulerian or Hamiltonian
I know that $G$ is Eulerian iff all of the vertex degrees are even. So my thinking is that for any cycle graph $C_n$, its subdivision graph is Eulerian because each vertex has degree 2 and adding a ...
- 303
0
votes
1
answer
326
views
A connected graph G has 12 vertices and 64 edges. Is G Hamiltonian? Is G Eulerian? [closed]
A connected graph G has 12 vertices and 64 edges. Is G Hamiltonian? Is G Eulerian? Do we have enough information to be able to tell?
Not sure where to start with this one! Can anyone help me out?
- 3
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
2
votes
1
answer
155
views
Creating a $4 \times 4$ square grid using $5$ pieces of $8$-inch wires
We would like to create a $4$-by-$4$ square grid using pieces of wire such that the sides of the squares are $1$ inch and we are not allowed to cut the wires. Is it possible to create the grid by ...
- 79
0
votes
0
answers
93
views
How can I find a cyclic path in a graph
Is there any algorithm or approach to find a cyclic path within a graph, optimizing some cost function, e. g. maximizing a reward associated with edges. The optimal cyclic path would then be the one ...
- 301
1
vote
1
answer
198
views
Are Euler trails and tours of a graph the same as Hamilton paths and cycles of the corresponding "edge graph"?
Is knowing information about Euler paths and Euler tours about a graph $G$ the same as knowing information about Hamilton paths and cycles of the graph $H$ obtained from $G$ such that vertices of $H$ ...
- 2,649
0
votes
1
answer
447
views
Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit
Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit?
I know the answer is yes, but if you consider something like this:
I don't think this would be bipartite, ...
- 35
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