| 查看: 338 | 回复: 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. |
回复此楼» 猜你喜欢
什么是人一生最重要的？
已经有6人回复
-
为什么中国大学工科教授们水了那么多所谓的顶会顶刊，但还是做不出宇树机器人？
已经有11人回复
-
网上报道青年教师午睡中猝死、熬夜猝死的越来越多，主要哪些原因引起的？
已经有9人回复
-
【博士招生】太原理工大学2026化工博士
已经有5人回复
-
280求调剂
已经有3人回复
-
面上可以超过30页吧？
已经有11人回复
-
版面费该交吗
已经有15人回复
-
体制内长辈说体制内绝大部分一辈子在底层，如同你们一样大部分普通教师忙且收入低
已经有18人回复
★
小木虫: 金币+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