Name
Abstract | ||
|---|---|---|
We investigate a new type of graph inequality (in the tradition of Cvetkovic, Simic, and Capobianco) which is based on the subgraph relation and as terms allows fixed graphs, graph variables with specified vertices, and the operation of identifying vertices. We present a simple such inequality which does not have a solution, though not obviously so, 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/S0895480199360655 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
specified vertex,simple graph inequality,graph inequalities,subgraph relation,nondeterministic exponential time,new type,new york acad,graph theory,graph inequality,technische hochschule ilmenau,graph variable,discrete mathematics,directed graph,decidability,vertex | Discrete mathematics,Combinatorics,Line graph,Graph homomorphism,Cycle graph,Distance-hereditary graph,Null graph,Factor-critical graph,Mathematics,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
19 | 3 | 0895-4801 |
Citations | PageRank | References |
1 | 0.38 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcus Schaefer | 1 | 123 | 12.63 |
| Daniel Stefankovic | 2 | 243 | 28.65 |