Просмотр кода страницы Induced matching partition number

'''Induced matching partition number''' --- число разбиения
индуцированного паросочетания. 

The '''induced matching partition number''' of a graph <math>G</math>, denoted
<math>imp(G)</math>, is the minimum integer <math>k</math> such that <math>V(G)</math> has a
<math>k</math>-partition <math>(V_{1}, \ldots, V_{k})</math> such that, for each <math>i</math>, <math>1
\leq i \leq k</math>, <math>G[V_{i}]</math>, the subgraph of <math>G</math> induced by <math>V_{i}</math>, is
1-regular graph. It is known that, if <math>G</math> is a graph which has a ''perfect matching'', then <math>imp(G) \leq 2\Delta(G) - 1</math>, where
<math>\Delta(G)</math> is the maximum degree of a vertex of <math>G</math>. Furthermore,
<math>imp(G) = 2\Delta(G) - 1</math> if and only if <math>G</math> is isomorphic to either
<math>K_{2}</math> or <math>C_{4k+2}</math> or the '' Petersen graph'', where <math>C_{n}</math> is the cycle of length <math>n</math>.