On vertex-weighted realizations of acyclic and general graphs

Consider the following natural variation of the degree realization problem. Let be a simple undirected graph of order . Let be a vector of vertex , and let be a vector of at the vertices. Then on if the constraints are satisfied for all , where denotes the neighbourhood of vector . Given a requirements vector , the problem asks for a suitable graph and a vector of provided services that satisfy on .In this paper, we consider two avenues. We initiate a study that focuses on weighted realizations where the graph is required to be of a specific class by providing a full characterization of realizable requirement vectors for paths and acyclic graphs. However, checking the respective criteria is shown to be NP-hard.In the second part, we advance the study in general graphs which was started in . For the unsolved cases, the question of whether a vector is realizable can be formulated as whether its largest requirement lies within certain intervals. We describe several new, realizable intervals and show the existence of an interval that cannot be realized. The complete classification for general graphs is an open problem.