Could anyone provide me with a list of graph properties that are regular? I do not mean the definition of a regular graph, I mean graph PROPERTIES.
Why am I asking this? Well, while revisiting the whole discussion on the Chomsky hierachy for formal languages, its possible translation into graphs, and the impact on automata, I found reflections from experts regarding the following question:
Wwhich properties of a graph can be recognized by a finite deterministic automaton? Or, in other words, which properties of a graph are regular?
Apparently people claim that the first answer that comes to mind is not many, if any, given that such kind of automaton lacks memory.
So once I have explained the rationale behind my question, I will be glad to hear from you.
Best regards,
As Lee Mosher pointed out, your question is not very explicit. Nevertheless, I think that you might be interested in this article:
J. Engelfriet, A regular characterization of graph languages definable in monadic second-order logic. Theoret. Comput. Sci. 88 (1991), no. 1, 139--150.
However, the most important result in that direction is Courcelle's theorem about monadic second order definable graphs.