「完全2部グラフ」の版間の差分
削除された内容 追加された内容
→特性: 完全二部グラフはムーアグラフではなし、かつCageでもない。 |
|||
32行目:
* 2部グラフから、辺数 <math>m\cdot n</math> が最大となる完全2部部分グラフ <math>K_{m,n}</math> を求める問題は、[[NP完全問題]]である。
* [[平面グラフ]]は <math>K_{3,3}</math> を[[マイナー (グラフ理論)|マイナー]]として含むことができない。外平面 (outerplanar) グラフは <math>K_{3,2}</math> をマイナーとして含むことができない（これらは平面性や外平面性の十分条件ではないが、必要条件である）。
* 完全2部グラフ <math>K_{n,n}</math> は[[ムーアグラフ]]であり、<math>(n,4)</math>-[[:en:cage (graph theory)|cage]] である。
* 完全2部グラフ <math>K_{n,n}</math> または <math>K_{n,n+1}</math> は [[:en:Turán graph|Turán graph]] である。
* 完全2部グラフ <math>K_{m,n}</math> の[[頂点被覆|頂点被覆数]]は <math>\min \lbrace m,n \rbrace</math>、[[辺被覆数]]は <math>\max\lbrace m,n\rbrace</math> である。
| |||