按类别列出问题

Mathematics


计算数学 >> 离散数学 >> 图论
Questions in category: 图论 (Graph Theory).

1

chromatic number

Posted by haifeng on 2014-04-14 09:22:08 last update 2014-04-14 09:22:47 | Answers (0) | 收藏

将一个图 $G$ 的各顶点着色, 使相邻顶点不同颜色的最少颜色数, 称为该图的 chromatic number.

 


References:

http://mathworld.wolfram.com/ChromaticNumber.html

2

[Thm]Cayley 图的笛卡尔乘积仍为 Cayley 图

Posted by haifeng on 2011-08-19 08:55:21 last update 2011-08-19 08:55:21 | Answers (0) | 收藏

该结果由徐俊明, 徐克力所证明.

References
徐俊明, 徐克力. Cayley 图的笛卡尔乘积, 中国科学技术大学学报 Vol.31, No.6, Dec. 2001, 635--640.

3

[Def]Cayley 图的定义

Posted by haifeng on 2011-08-19 08:50:35 last update 2011-08-19 08:50:35 | Answers (0) | 收藏

假设 $\Gamma$ 是一个非平凡有限群, $S$ 是 $\Gamma$ 的非空子集, 且不含单位元. 定义一个有向图 $G$ 如下:

\[ V(G)=\Gamma;\quad (x,y)\in E(G)\Leftrightarrow x^{-1}y\in S,\ \forall\ x,y\in\Gamma. \]

称 $G$ 为群 $\Gamma$ 关于子集 $S$ 的 Cayley 图, 记为 $C_\Gamma(S)$.

4

[Def] n 个图的笛卡尔乘积

Posted by haifeng on 2011-08-19 08:34:33 last update 2011-08-19 10:58:41 | Answers (0) | 收藏

假设 $G_i=(V_i,E_i),\ i=1,2,\ldots,n$ 是 $n$ 个图, 它们的笛卡尔乘积 $G=G_1\times G_2\times\cdots\times G_n$ 定义为, $V(G)=V_1\times V_2\times\cdots\times V_n$, 且 顶点 $(x_1,x_2,\ldots,x_n)$ 与 $(y_1,y_2,\ldots,y_n)$ 之间存在一条边当且仅当这两个顶点(向量)的坐标仅有一个分量是不同的, 比如 $x_{i_0}\neq y_{i_0}$, 并且 $(x_{i_0},y_{i_0})\in E_{i_0}$.

5

Hamiltonian Weight Conjecture

Posted by haifeng on 2011-08-09 08:37:06 last update 2011-08-09 08:37:06 | Answers (0) | 收藏

http://www.math.uiuc.edu/~west/openp/cqhamwt.html

6

亏格为 $g$ 的二维曲面上地图着色的最少颜色数公式

Posted by haifeng on 2011-05-07 15:33:07 last update 0000-00-00 00:00:00 | Answers (0) | 收藏

希伍德(Heawood)的猜想

Search

New posted more ...