236 reputation
15
bio website vinicius.ime.uerj.br
location Brazil
age 29
visits member for 2 years, 2 months
seen Jun 6 at 2:09

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.