Timeline for Strongly connected DAG from any connected undirected graph?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2014 at 12:50 | comment | added | Emil Jeřábek | No problem. I’m sorry for the needlessly irritated reaction. | |
| Jul 3, 2014 at 16:42 | comment | added | Joel David Hamkins | Oh, dear, my apologies! I didn't mean my comment to be taken as criticism---I shall hide from the straw man behind my "if"---but rather only to add commentary concerning the situation with infinite graphs, a situation in which I am very interested. | |
| Jul 3, 2014 at 16:05 | comment | added | Emil Jeřábek | @Joel: Given the context, I am assuming that graphs are finite by definition, as usual in discrete mathematics. I would be extremely surprised if that’s not what the OP intended. Anyway, I never said anything about integers, so please be that kind and do not put words in my mouth, or at least if you do, choose an interpretation that spares lives of innocent straw men. | |
| Jul 3, 2014 at 15:29 | comment | added | Joel David Hamkins | @Emil, if "number" here means natural number or integer, then your equivalence, although true for finite graphs, is not true for all infinite graphs, since some infinite acyclic digraphs cannot be $\mathbb{Z}$-graded (such as the digraph of the usual $\leq$ relation on $\mathbb{Q}$). Meanwhile, a countable digraph is acyclic if and only if it can be $\mathbb{Q}$-graded, and in general, any digraph is acyclic just in case it is graded by some linear order. | |
| Jul 3, 2014 at 13:24 | answer | added | Joel David Hamkins | timeline score: 4 | |
| Jul 3, 2014 at 12:16 | comment | added | Emil Jeřábek | As for question 2, a directed graph is acyclic if and only if there is a numbering of its vertices satisfying the condition in the first sentence. This has nothing to do with connectedness. | |
| Jul 3, 2014 at 11:19 | comment | added | David Handelman | Strongly connected (for a directed graph) usually means that between any two vertices there exist directed paths from one to the other; frequently, this is called diconnected. A possible counter-example (if I've understood the question correctly) is the edge and vertex set of the unit cube. | |
| Jul 3, 2014 at 11:03 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
fix markup
|
| Jul 3, 2014 at 10:37 | answer | added | user44191 | timeline score: 3 | |
| Jul 3, 2014 at 10:28 | comment | added | user44191 | What you mean by "strongly connected" doesn't seem to be the standard usage; an a cyclic graph can only be strongly connected if it has one vertex. I've answered below assuming I understood what you mean by "strongly connected" correctly. You also seem to have dropped your second question. | |
| Jul 3, 2014 at 9:09 | history | asked | user32851 | CC BY-SA 3.0 |