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.
Done