Alladi Ramakrishnan Hall

Graph Transit Functions, Characterizations and Impossibility Results on First Order Axioms

Manoj Changat

University of Kerala

In this talk, well known path transit functions, namely, the interval function (defined using shortest paths), Induced path function (defined using induced paths) and the all path functions (defined using all paths) on graphs are discussed. We discuss axiomatic characterizations of the interval function and the all paths transit function on arbitrary simple graphs using first order axioms and the impossibility result of characterization using first order axioms for the induced path function. We also discuss some graph classes which possess and some which do not possess this kind of axiomatic characterization (of the interval function). We also mention some interesting open problems.