A two-vertex digon counterexample and an oriented local descent theorem
Statement
Conjecture 6.14. For any k and any digraph G, define G∗ to be those vertices with |N +2 (v)| ≥ |N+(v)|. Then any vertex of out-degree k is at distance at most k from a vertex in G∗.Notes: He motivates this with the following remark: "If a vertex x has one successor y, then if y has no successors, y ∈ G∗, otherwise x ∈ G∗. This property seems to generalize for any out-degree, and if it is true, is optimal considering 'pyramids' where any vertex of out-degree k
is at distance exactly k from the (unique) solution." His 'pyramids' are formed by placing one vertex, then two in the row beneath it, and so forth ( i vertices in row i) to form a triangle. The vertices in row i are then completely joined to all vertices in row i − 1 for i ≥ 2.
Record
- Source
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.