What is a T-star packing and what is Proper Maximal 3-Star Packing? I read some definitions and can't understand

"By a T-star we mean a complete bipartite graph K1,t for some t ≤ T. For an undirected graph G, a T-star packing is a collection of node-disjoint T-stars in G."

  • 2
    $\begingroup$ What in particular is confusing here? $\endgroup$
    – Juho
    Jul 16, 2021 at 7:03

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.