Prev: Question on Sipser example proof
Next: FCT 2009 conference known?
From: Zhu Guohun on 4 Jul 2008 23:07
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 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.

Is my mistake or his careless?
------------------------------------------------
Zhu
From: Ben Bacarisse on 5 Jul 2008 09:28
Zhu Guohun <ccghzhu(a)hrt.dis.titech.ac.jp> 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.
From: Zhu Guohun on 5 Jul 2008 23:07
On 7ÔÂ5ÈÕ, ÏÂÎç9ʱ28·Ö, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote:
> Zhu Guohun <ccgh...(a)hrt.dis.titech.ac.jp> 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.

Thank you for your answer.
Maybe it is not necessary to ask the reviewer

---------------------------------
Zhu
 | 
Pages: 1
Prev: Question on Sipser example proof
Next: FCT 2009 conference known?