Due to the ubiquity of graphs, graph analytics has attracted much attention from both research and industry communities. The notion of k-truss is widely used in graph analytics. Since graphs are continuously evolving in real applications and it is costly to compute trusses from scratch, we study the problem of truss maintenance which aims at designing efficient incremental algorithms to update trusses when graphs are updated with changes. An incremental algorithm is desired to be bounded; that is, its cost is of O(f(|CHANGED|_c)) for some polynomial function f and some positive integer c, where CHANGED comprises the changes to both the graph and the result and |CHANGED|_c is the size of the c-hop neighborhood of CHANGED. An incremental problem is bounded if it has a bounded incremental algorithm and is unbounded otherwise. Under the model of locally persistent algorithms, we prove that truss maintenance is bounded under edge removals but is unbounded even for unit edge insertions. To address the unboundedness, we formulate a new notion AFF^preceq which, as a practically effective alternative to CHANGED, represents a set of edges affected by the changes to the graph, and devise an insertion algorithm that is bounded with respect to AFF^preceq, while retaining the boundedness for edge removals. More specifically, our insertion algorithm runs in O(f(|AFF^preceq|_c)) time for some polynomial function f and some positive integer c with |AFF^preceq|_c being the size of the c-hop neighborhood of AFF^preceq. Our extensive performance studies show that our new algorithms can significantly outperform the state-of-the-art by up to 3 orders of magnitude for the 12 large real graphs tested and are more efficient than computing trusses from scratch even for changes of non-trivial size. We report our findings in this paper.