The induced path function, monotonicity and betweenness |
| |
Authors: | Manoj Changat |
| |
Institution: | a Department of Futures Studies, University of Kerala, Trivandrum-695 034, India b Department of Mathematics, S.B. College, Changanassery-686 101, India c Econometrisch Instituut, Erasmus Universiteit, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands |
| |
Abstract: | The geodesic interval function I of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský 20]. Surprisingly, Nebeský 23] showed that, if no further restrictions are imposed, the induced path function J of a connected graph G does not allow such an axiomatic characterization. Here J(u,v) consists of the set of vertices lying on the induced paths between u and v. This function is a special instance of a transit function. In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of J. The function J satisfies betweenness if w∈J(u,v), with w≠u, implies u∉J(w,v) and x∈J(u,v) implies J(u,x)⊆J(u,v). It is monotone if x,y∈J(u,v) implies J(x,y)⊆J(u,v). In the case where we restrict ourselves to functions J that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of J by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs. |
| |
Keywords: | Transit function Induced path Betweenness Monotone Long cycle House Domino _method=retrieve& _eid=1-s2 0-S0166218X09003916& _mathId=si22 gif& _pii=S0166218X09003916& _issn=0166218X& _acct=C000051805& _version=1& _userid=1154080& md5=aa72e437806c1d840d6521a6bcb204ab')" style="cursor:pointer P-graph" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">P-graph |
本文献已被 ScienceDirect 等数据库收录! |
|