| 查看: 313 | 回复: 1 | |||
gen007gen木虫 (正式写手)
|
[交流]
Interesting Open Problems Related to Graphs Thoery 已有1人参与
|
|
The following conjecture was proposed by P. Seymour in 1990. Conjecture: every directed graph $D=(V, A)$ (loopless and without multiple arcs or circuits of length two) contains a vertex $v$ such that $|N^+(v)|\leq |N^{++}(v)|$, where $N^+(v)$ is the set of all out neighbors of $v$ and $N^{++}$ is the set of all second out neighbors of $v$, that is, $N^+(v)=\{u\mid (v,u)\in A\}$ and $N^{++}=\{u\in V\setminus N^+(v)\mid \exists {u'\in N^+(v) [(v,u')\in A, (u', u)\in A]} \}$. Fisher [1] has proved that the conjecture is true when $D$ is a tournament. However, for $D$ being a general digraph, this conjecture remains open. [1] D. C. Fisher, Squaring a tournament: a proof of Dean’s conjecture. J. Graph Theory, 23 (1996), 43–48. |
回复此楼» 猜你喜欢
Materials Today Chemistry审稿周期
已经有4人回复
-
萌生出自己或许不适合搞科研的想法，现在跑or等等看？
已经有3人回复
-
参与限项
已经有3人回复
-
假如你的研究生提出不合理要求
已经有7人回复
-
实验室接单子
已经有4人回复
-
全日制（定向）博士
已经有4人回复
-
对氯苯硼酸纯化
已经有3人回复
-
求助:我三月中下旬出站，青基依托单位怎么办？
已经有12人回复
-
所感
已经有4人回复
-
要不要辞职读博？
已经有7人回复
★
小木虫: 金币+0.5, 给个红包，谢谢回帖
小木虫: 金币+0.5, 给个红包，谢谢回帖
|
Interesting Open Problems Related to Graphs Thoery 以图形理论相关的有趣的开放问题 The following conjecture was proposed by P. Seymour in 1990. 以下猜想是由P.西摩1990了。 Conjecture: every directed graph $D=(V, A)$ (loopless and without multiple arcs or circuits of length two) contains a vertex $v$ such that $|N^+(v)|\leq |N^{++}(v)|$, where $N^+(v)$ is the set of all out neighbors of $v$ and $N^{++}$ is the set of all second out neighbors of $v$, that is, $N^+(v)=\{u\mid (v,u)\in A\}$ and $N^{++}=\{u\in V\setminus N^+(v)\mid \exists {u'\in N^+(v) [(v,u')\in A, (u', u)\in A]} \}$. 猜想：每一个有向图$ d =（V，A）$（无环和不多的弧或电路的长度）包含一个顶点v，|美元美元美元^ + n（V）| \ LEQ | N ^ { + }（V）|美元，其中$ n ^ +（V）是集所有邻居的$ V $和$ N ^ { + } $是集所有第二邻居五美元，美元，美元，N ^ +（V）= \ {U \中期（v，u）\ \ } $和$ N ^ { + } = \ { u在V型setminus N ^ +（V）\中\存在{ U \ n ^ +（V）[（v，u）在一，（u，u）在一] } } $ \。 Fisher [1] has proved that the conjecture is true when $D$ is a tournament. However, for $D$ being a general digraph, this conjecture remains open. 费舍尔[ 1 ]证明猜想为真时$ D $是一个比赛。然而，为$ D $作为一种通用的有向图，这个猜想仍然是开放的。 [1] D. C. Fisher, Squaring a tournament: a proof of Dean’s conjecture. J. Graph 【1】D. C. Fisher，蕾比赛：Dean猜想的证明。J.图 Theory, 23 (1996), 43–48. 理论上，23（1996），43–48。 这个是翻译，供参考 不一定100%准确，见谅 |
2楼2013-03-04 19:06:42