| 查看: 404 | 回复: 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. |
回复此楼» 猜你喜欢
什么时候开奖？
已经有11人回复
-
范进中举一文的中心思想
已经有6人回复
-
建议基金发布提前给出明确的时间点
已经有14人回复
-
2026国自然函评费到账
已经有17人回复
-
让我中一个面上吧！
已经有15人回复
-
2026年的国家社科基金项目通讯评审的新规则与新动向、新挑战
已经有5人回复
-
跳槽后在研项目怎么办？
已经有10人回复
-
今天放榜吗？
已经有16人回复
-
93BebMhtakh前后11位开头都是大写
已经有8人回复
-
只有每年这种时候来逛逛小木虫
已经有26人回复
★
小木虫: 金币+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
