We investigate a new type of graph inequality (in the tradition of Cvetkovic, Simic, and Capobianco) which is based on the subgraph relation and which allows as terms fixed graphs, graph variables with specified vertices, and the operation of identifying vertices. We present a simple graph inequality which does not have a solution, and show that the solvability of inequalities with only one graph variable and one specified vertex can be decided (in nondeterministic exponential time). The solvability of graph inequalities over directed graphs, however, turns out to be undecidable.
The paper is online at http://www.cs.uchicago.edu/publications/tech-reports/TR-99-05.ps.