Vinicius dos Santos
Reputation
261
Top tag
Next privilege 500 Rep.
Access review queues
 Mar 7 comment existence of spanning trees in complete graphs implies choice? But didn't you use the axiom of choice in order to pick a vertex $u$? Mar 7 comment Number of edges in a digraph? This should be turned into an answer so that the question appears as answered for the community. Apr 17 comment Eccentricity of vertices in a graph Since k >= |V(G)|/2, if you take non-adjacent vertices u and v, you have |N(u)|+|N(v)|>= |V(G)|. Note that the total number of vertices is as big as the vertex set, hence, since they are not adjacent, there must be a repetition between the vertices of N(u) and N(v). Apr 9 comment Eccentricity of vertices in a graph There are some trivial restrictions like the degree equals to |V(G)|-1 or |V(G)|-2. Is that the kind of restriction you are looking for? Apr 5 comment Diameter of $k$-regular graph Sure! Stupid me. I will fix it. Apr 5 comment Diameter of $k$-regular graph Is this true? Is it bounded by n/k or O(n/k)? Oct 15 comment Conditional merge of a sequence of DAGs / partial orders As I said, I'm not sure the problem can be solved efficiently. It wouldn't surprise me if it's NP-hard.