# parameterized complexity – What is T-star packing

So a $$t$$-star is the graph you get by taking one central node and connecting $$t$$ neighbors to it. Equivalently, a $$t$$-star is the complete bipartite graph $$K_{1,t}$$ if you wish to express it like that as your definition does.

A $$t$$-star packing then is a bunch of such $$t$$-stars found from some graph $$G$$ so that their nodes don’t overlap. As a simple example, consider the 4-cycle. You can find a 1-star packing of size 2 in it: take one edge as the other 1-star, and the other edge as the other 1-star.

The packing described above is maximal: you can’t extend it by adding a new member (i.e., a third 1-star) into it. It also happens to be maximum, i.e., it is the largest such packing you can find. I encourage you to think about what the difference between a maximal and maximum packing is, i.e., find an example where they differ.

I don’t what proper here means, but it is likely defined in your source.

Posted on Categories Articles