Re: How many edges are there in semi cubic digraph

Zhu Guohun <ccghzhu@xxxxxxxxxxxxxxxxxxxx> writes:

How to understand follow digraph:
" a simple strong connected digraphs with at most indegree 1 or 2 and
outdegree 2 or 1 respectively" (let named it as semi cubic
digraph)

I find this way of writing it rather confusing. I think its is
simpler to talk about a "simple, strongly-connected digraph with degree
at most three". If any node of degree three as all the edges as in
or out, then the graph can't be strongly connected.

I think there are at most m=3n/2 edges existance in the semi cubic
digraph with n vertecies

But a reviewer think that a cycle digraph should be m=2n arcs so
that my opinion is mistaken.

As far as I can tell (I am no expert) you are right. Can you ask for
counter-example?

--
Ben.
.

Relevant Pages