First-Order Logic with Connectivity Operators

Connectivity is one of several properties that cannot be expressed in first-order logic (FO). We introduce a new logic, called FO+Conn, that has atomic operators Conn_k that can express connectivity in undirected graphs when up to k vertices (that we can quantify) have been deleted. We study the expressive power of the new logic and the complexity of its model-checking problem.

Authors

• Nicole Schrader

Keywords

No keywords are indexed for this paper.