All Questions
4 questions
0
votes
0
answers
36
views
A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial
We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle.
Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...
- 4,058
0
votes
0
answers
125
views
Are there any necessary conditions of the existence of a Hamiltonian cycle on directed graphs
I'm trying to prove that one concrete directed graph has no Hamiltonian cycle, but didn't seem to find any relevant theorems
5
votes
1
answer
1k
views
How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?
The question started from a problem brought home by a friend's 5th grader: "How many ways can you seat 5 people around a round table so that the people sitting to the left of any person is different ...
- 2,205
16
votes
1
answer
696
views
A counterexample to a conjecture of Nash-Williams about hamiltonicity of digraphs?
Maybe I am missing something, but found potential counterexample to a conjecture
of Nash-Williams.
According to HAMILTONIAN DEGREE SEQUENCES IN DIGRAPHS
The outdegree and indegree sequences of ...
- 25.4k