Apologies for if this is a rather silly question, but the impetus for this question comes from the curious usage of the titular phrase within this conference paper right after the section entitled "2 The General Approach" at the top of page 273. For full context, the sentence in question reads:
If the given tree is not rooted or binary, we can root it at an arbitrary vertex or make it binary by adding a linear number of vertices and edges of weight zero as in [29].
Where [29] is a citation to the hyperlink as I've set it as here.
My question is, what exactly is meant by "adding a linear number of" some object to some other object in a mathematical context? I don't believe I've encountered such phrasing before, and subsequent searches for other examples via Google didn't really provide any further elaboration on the contextual meaning.
Now, from a general perspective, I see that this phrase somehow conveys the procedure that transforms a non-binary mathematical tree into a binary one. Honestly, as someone who is fairly new to the area of graph theory, I'm having trouble figuring out how it is possible to turn a $(2+n)$-ary tree with $n \in \Bbb N$ into a binary tree, so I think that this is the point at which I get stuck trying to elucidate the definition of the phrase by showing what its application should result in.
All of the above reasoning aside, I can't help but feel that it just may simply be a slight notational quirk in the phrasing itself. That is, the phrase "add a discrete number of X" clearly indicates to add some single-valued amount of X to whatever it is that is being discussed. Could it then be that the titular phrase indicates simply to add some "linear" amount of X to the discussed object, which perhaps translate to "add some linear combination of X's to Y"?
Although the above thinking seems like a plausible answer to me, I'd like to be sure about it. Additionally, even if I have figured out what the titular phrase means, I wouldn't want to have missed some sort of "implied" nuance related to the phrase itself that isn't so obvious after a simple, cursory glance.
"A linear number of vertices and edges" presumably means, "sets of vertices and edges whose cardinality is a linear function of ... [something else]." I'm not sure what the [something else] is in your example, but probably the number of nodes.
Essentially, when you are transforming one graph object to another, it is often of interest to know by how much you are increasing the size of the object. For example, if you have a tree with $n$ nodes and you transform it to another tree that has $O(2^n)$ nodes, that might not be a useful transformation, even if the new tree has some other nice property. In your case, it seems that the new tree has $O(n)$ new nodes and edges—so, not too bad.