Independence subdivision number

Independence subdivision number --- независимое число подразбиения.

The independence subdivision number [math]\displaystyle{ sd_{\beta}(G) }[/math] of a graph [math]\displaystyle{ G }[/math] is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the independence number. It is known that for any graph [math]\displaystyle{ G }[/math] of order [math]\displaystyle{ n \geq 2 }[/math], either [math]\displaystyle{ G = K_{1,m} }[/math] and [math]\displaystyle{ sd_{\beta}(G) = m }[/math], or

[math]\displaystyle{ 1 \leq sd_{\beta}(G) \leq 2. }[/math]

See also

• Domination subdivision number.