Let S ⊆ V be an arbitrary subset of vertices of a graph G = (V,E). The differential ∂(S) of S equals the difference between the number of vertices in V \ S that are adjacent to vertices in S and the number of vertices in S. A nonempty set S is called a balanced set if ∂(S) = 0. In this paper we introduce the study of balanced sets in graphs. Not all graphs have balanced sets, and such graphs are called unbalanced. We give proofs of the existence of balanced sets in various kinds of graphs, such as even order graphs, bipartite graphs, and graphs of maximum degree three. We also investigate unbalanced graphs.

Empty answers are a major problem by processing pattern matching queries in graph databases. Especially, there can be multiple reasons why a query failed. To support users in such situations, differential queries can be used that deliver missing parts of a graph query. Multiple heuristics are proposed for differential queries, which reduce the search space. Although they are successful in increasing the performance, they can discard query subgraphs relevant to a user. To address this issue, the authors extend the concept of differential queries and introduce top-k differential queries that calculate the ranking based on users’ preferences and significantly support the users’ understanding of query database management systems. A user assigns relevance weights to elements of a graph query that steer the search and are used for the ranking. In this paper the authors propose different strategies for selection of relevance weights and their propagation. As a result, the search is modelled along the most relevant paths. The authors evaluate their solution and both strategies on the DBpedia data graph.