%\documentclass[12pt,fleqn,titlepage,twoside]{thesis}%{book}%{thesis}%{book},
%\documentclass[12pt,fleqn,titlepage]{book}
%\documentclass[12pt,A5,oneside]{book}
%\documentclass[a5paper,headsepline,titlepage,12pt,normalheadings]{thesis}
%\usepackage[a5paper]
\documentclass[12pt,fleqn,titlepage,oneside]{thesis}
\usepackage{amsfonts,epsf,amsmath,amssymb,latexsym}
\usepackage[sans]{dsfont}

%\usepackage[a5paper]{geometry}

\usepackage{float}
\usepackage{graphicx}
\usepackage{makeidx}
\usepackage{pstricks}
%\usepackage{pstricks}
\usepackage{pst-plot}
%\usepackage[]{color}
%\usepackage[letterpaper,colorlinks,breaklinks,backref]{hyperref}
%\usepackage{hyperref}
\usepackage{textcomp}
\usepackage{epsfig}
%\usepackage{cite}
\usepackage[T1]{fontenc}
\usepackage[cp1250]{inputenc}
\usepackage[]{color}
%\usepackage[letterpaper],colorlinks,breaklinks,backref]{hyperref}
%\usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true, %colorlinks=true,backref=true%]%
%]{hyperref}
%\usepackage[notref,notcite]{showkeys}
\usepackage{setspace}

%\usepackage{natbib}

%\bibpunct{(}{)}{;}{a}{,}{,}

% Centering the EPS graphics inside the FIGURE environment

\def\slika #1{\begin{center} \epsffile{#1} \end{center}}
\makeindex

\newcommand{\proof}{\noindent{\bf Proof.\ }}
\newcommand{\qproof}{\noindent{\bf Dokaz.\ }}
\newcommand{\qed}{\hfill $\Box$ \bigskip}

\newcommand{\diam}{\rm diam}
\def\cp{\,\square\,}
\def\tc{$\Theta$-class }
\def\tcs{$\Theta$-classes }
\def\pc{partial cube }
\def\pcs{partial cubes }
\def\fab{$F_{ab}$ }
\def\fac{$F_{ac}$ }
\def\fcd{$F_{cd}$ }
\def\wab{$W_{ab}$ }
\def\wba{$W_{ba}$ }
\def\wcd{$W_{cd}$ }
\def\wdc{$W_{dc}$ }
\def\uab{$U_{ab}$ }
\def\uba{$U_{ba}$ }
\def\di{{\rm dim_I}}
\def\dl{{\rm dim_L}}
\def\dt{{\rm dim_T}}
\def\dm{{\rm diam}}
\def\cp{\,\square\,}
\newcommand{\id}{\ensuremath{I^\Delta}\,}
\newcommand{\io}{\ensuremath{I_1}\,}
\newcommand{\e}{\ensuremath{E(G)}\,}
\newcommand{\3}{\ensuremath{b3^\prime}}
\newcommand{\del}{\ensuremath{\delta(G)}}
\newcommand{\peri}{\ensuremath{Per(G)}}
\newcommand{\ct}{\ensuremath{Ct(G)}}
\newcommand{\ecc}{\ensuremath{Ecc(G)}}


\newtheorem{theorem}{\bf Theorem}[chapter]
\newtheorem{qtheorem}[theorem]{Izrek}
\newtheorem{qproposition}[theorem]{Trditev}
\newtheorem{problem}[theorem]{\bf Problem}

\newtheorem{proposition}[theorem]{\bf Proposition}
\newtheorem{lemma}[theorem]{\bf Lemma}
\newtheorem{exam}[theorem]{\bf Example}
\newtheorem{qlemma}[theorem]{Lema}
\newtheorem{conjecture}[theorem]{\bf Conjecture}
\newtheorem{cor}[theorem]{\bf Corollary}
\newtheorem{qcorollary}[theorem]{Posledica}
\newtheorem{remark}[theorem]{\bf Remark}
\newtheorem{defi}[theorem]{\bf Definition}
\newtheorem{obs}[theorem]{\bf Observation}
\newenvironment{wlist}
{\vspace{-15pt}
\begin{list}{}
{\setlength{\labelwidth}{15mm}
\setlength{\partopsep}{0pt}
\setlength{\parskip}{0pt}
\setlength{\topsep}{0pt}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\labelsep}{10pt}
\setlength{\leftmargin}{15mm}}
\item[]}
{\end{list}
\vspace{2pt}
\smallskip}

\setlength{\voffset}{-10pt}
\setlength{\topmargin}{10pt}
\setlength{\headheight}{14pt}
\setlength{\headsep}{25pt}
\setlength{\textheight}{660pt}
\setlength{\footskip}{30pt}
\setlength{\hoffset}{0pt}
\setlength{\oddsidemargin}{1.4cm}
\setlength{\textwidth}{426pt}
\setlength{\marginparsep}{0pt}
\setlength{\marginparwidth}{0pt}
\setlength{\marginparpush}{0pt}
%\setlength{\headwidth}{\textwidth}
\setlength{\evensidemargin}{\paperwidth}
\addtolength{\evensidemargin}{-\textwidth}
\addtolength{\evensidemargin}{-2.0in}
\addtolength{\evensidemargin}{-\oddsidemargin}

%\usepackage[Lenny]{fncychap}

\begin{document}


\frontmatter

\bigskip \thispagestyle{empty}
\begin{titlepage}
\begin{center}
\Large{\bf A STUDY OF BETWEENNESS USING SOME METRIC RELATED TRANSIT FUNCTIONS ON GRAPHS}\\
\smallskip
\vspace{3.5cm}
\textit{Thesis submitted to the University of Kerala\\ for the award of the degree of\\Doctor of Philosophy in Mathematics}\\
\vspace{4cm}
\textbf{G. N. Prasanth}\\
\vspace{4cm}
\textit{Under the supervision of}\\
\vspace{1.5cm}
\textbf{Dr. Manoj Changat}\\
\texttt{Department of Futures Studies\\University of Kerala\\Thiruvananthapuram\\ 2009}
\end{center}

\end{titlepage}
\thispagestyle{empty}\pagebreak \noindent \texttt{Dr. MANOJ
CHANGAT\let\thefootnote\relax\footnotetext{Ph.
91471305321(Off.)2742309(Res.),305178(Fax), E\-mail:
mchangat@gmail.com} \hfill DEPARTMENT OF FUTURES
STUDIES\\READER\raggedright\hfill UNIVERSITY OF KERALA\\\hfill
THIRUVANANTHAPURAM - 34\\\hfill KERALA, INDIA} \vspace{5cm}
\begin{center}
\textbf{CERTIFICATE}\\
\end{center}

 \begin{spacing}{1.5}
This is to certify that the thesis entitled \textbf{``A Study of
Betweenness Using Some Metric Related Transit Functions on Graphs''}
submitted for the award of the degree of Doctor of Philosophy of the
University of Kerala is a record of bonafide research carried out by
Mr. G.N. Prasanth under my supervision.
No part of this thesis has been submitted for the award of any degree before.\\\\\\
\end{spacing}
\begin{flushright}
  \textit{Manoj Changat}
\end{flushright}
\newpage
\thispagestyle{empty}
%\pagebreak
~~\vspace{5cm}
\begin{center}
\textbf{DECLARATION}
\end{center}

 \begin{spacing}{1.5}
 I, G.N. Prasanth, do hereby declare that the thesis entitled \textbf{``A Study of Betweenness Using Some
  Metric Related Transit Functions on Graphs''} is a bonafide
   record of research done by me and this thesis or any part thereof has not been submitted by me for
   the award of any other degree, diploma, title or recognition before.\\\\\\
 \end{spacing}
 \begin{flushright}
  \textit{G.N. Prasanth}
\end{flushright}
\newpage
\thispagestyle{empty}
%\pagebreak
%~~\vspace{5cm}
\begin{center}
\textbf{ACKNOWLEDGEMENT}
\end{center}
\begin{spacing}{1.5}
First and foremost, I express my profound gratitude to my guide and
mentor Dr. Manoj Changat whose able guidance and seamless
encouragement helped me in successfully completing this work.

I express my sincere thanks to Dr. Joseph Mathews (former Head,
Department of Mathematics, S. B. College Changanacherry), for the
fruitful and encouraging discussions that helped to finalize many
results of this work.

My indebtedness to Dr. B. Kannan (Department of Computer
Applications, CUSAT), who immensely helped me with inputs and
suggestions through out the course of my work and also to solve one
of the theorems in Chapter 2 in the last phase of this research work
is expressed herewith.

I express my deep sense of gratitude to Professor Sandi Klav\v{z}ar,
Faculty of Mathematics and Physics, University of Ljubljana,
Slovenia for inviting me for a short visit to Slovenia under the
bilateral Indo- Slovenian research project during the summer
holidays in 2008 and providing all right milieu for carrying out the
work.  I also express my sincere thanks to Dr. Matja\v{z} Kov\v{s}e
of the research group in Discrete Mathematics in University of
Maribor for fruitful mathematical discussions and providing me with
necessary research papers and materials.

I remember with extreme gratitude, Professor Bo\v{s}tjan Bre\v{s}ar,
Dr. Iztok Peterin, and Aleksandra Tepeh Horvat of the research group
in Discrete Mathematics in University of Maribor for helping me in
solving the problem for betweenness in the Steiner intervals that
ultimately formed the subject of Chapter 6.

I owe my deepest sense of gratitude to Dr. Raju, (Reader School of
Social Science M.G University), who helped my in fine tuning the
introduction and conclusion of this report.

I am deeply indebted to Dr. V. Nanda Mohan, Head, Department of
Futures studies for providing all facilities and encouragement to
carry out the research work.

I am grateful to Mr. S.P. Sanalkumar, Systems Analyst, Department of
Futures Studies for his valuable suggestions, encouragements and
timely advices throughout the research work.

I also acknowledge the holistic support given by Mr. Praveen Kumar,
Project Coordinator, Department of Futures Studies.

My thanks to Ms. Ajitha, Research Scholar, Department of Futures
Studies for helping me draw the pictures of the graphs that form
part of the report.

My indebtedness is recorded herewith to Dr. M. N. Parasuraman,
Lecturer in English, Govt. College, Chittur for devoting time to
read and provide apt corrections whenever necessary.

I am also remembering Dr. Ramesh Kumar, Lecturer, Department of
Mathematics, University of Kerala for examining the work and
providing necessary corrections.

Thanks are due to Antony Mathews, Research Scholar, Department of
Futures Studies and Lecturer, Department of Mathematics, S.B.
College Changanacherry for the support rendered to me.

My hear felt thanks to each and every member especially Sri. Shyma
Prasad(former A.O) , Sri Raj Mohan (A.O) and Librarian of Department
of Futures Studies, University of Kerala.

I acknowledge the seamless support offered to me by the collegues of
the Department of Mathematics, Govt. College, Chittur for their
constant support and encouragement throughout the course of work.

I would like to express my sincere thanks to the Principal Govt.
College, Chittur who, without the slightest hesitation offered all
possible support for the successful completion of this work.

I owe a lot to all my friends without whose encouragement and moral
support, this work would not have been completed.

Last, but not the least, to my family, who have been a pillar of
strength through out the period and their love and care helped me,
overcome the testing times.
\end{spacing}
\begin{flushright}
  \textit{G.N. Prasanth}
\end{flushright}
\tableofcontents
%\listoftables
\listoffigures
%%%%

\bigskip %\thispagestyle{empty}
\mainmatter
\chapter{Background of the research problem}
\doublespacing
\section{Introduction}

\section{Betweenness in Graphs}
\subsection{Steiner trees and Steiner intervals in graphs}



\section{Approaching the problem}



\section{Synopsis}


\chapter{Basic observations of transit functions and
betweenness}\label{basic observations of transit functions}

\section{Introduction}


\section{Preliminary concepts}\label{preliminary}

%convex if $I(u, v) \subseteq V (H)$ for any $u, v \in V(H)$.

\section{Transit functions, betweenness axioms and their
implications} \label{binary transit functons and implications}



\section{$n$-ary transit functions and betweenness }
\label{n-ary}


\subsection{Betweenness}\label{n-ary bet}


\newcommand\FN{\footnote{The results of this chapter is published in the paper:  "Manoj Changat, G.N. Prasanth and Joseph Mathews, Triangle path transit functions, betweenness and pseudo-modular graphs, Disc. Math. 309 (2009), pp. 1575-1583, doi.10.1016 \lowercase{j.disc}. 2008.1.02.043."}}
\chapter[$I^\Delta$ path transit function]{$I^\Delta$ path transit function\protect\FN}

\label{idelta path transit function}





\addcontentsline{toc}{chapter}{Bibliography}
\begin{thebibliography}{99}

\bibitem{ar-03} {\em S. Arora}: Approximation schemes for NP-hard geometric
optimization problems: a survey, Math. Program. 97 (2003) 43-69.

\bibitem{bana-32}
{\em S. Banach}: Th\'{e}orie des op\'{e}rations lin\'{e}aires,
Warsaw, 1932.

%\bibitem{band-89}
%{\em H.J. Bandelt }: Graphs with intrinsic $S_{3}$ convexities.
%J.Graph Theory {\em 13} (1989), 215--228.

\bibitem{bach-06}
{\em H.-J.~ Bandelt, Victor Chepoi}: The algebra of metric
betweenness I: Subdirect representation and retraction, European
Journal of Combinatorics (2006), doi:10.1016/j.ejc.2006.07.003

\bibitem{bach-08}
{\em H.-J. Bandelt, V. Chepoi}: The algebra of metric betweenness
II: axiomatics of weakly median graphs. Europ. J. Combin.29. (2008),
676--700.

%\bibitem{hbhm-88}{\em H.J. Bandelt, H.M. Mulder}: Regular pseudo median graphs.
%J.Graph Theory, {\em 12} (1988), 533--549.

%\bibitem{hme-94}
%{\em H.J. Bandelt, H.M. Mulder, E.Wilkeit}: Quasi median graphs
%and algebras. J.graph theory {\em 18}, (1994), 681--703.

\bibitem{besa-91}
{\em S. L. Bezrukov, A. Sali}: On superspherical graphs. Sets,
graphs and numbers, Colloq. Math. Soc. J\'{a}nos Bolyai 60 (1991)
89-95.

\bibitem{birk-40}
{\em G.D. Birkhoff}: Lattice theory, Amer. Math. Soc. Colloquium
Publications vol 25, 1940.

\bibitem{birk-32}
{\em G. D. Birkhoff}: A set of postulates for plane geometry based
on scale and protractor, Ann. Math., 33 (1932) 329–-345.

\bibitem{blbr}
{\em A.~Blokhuis, A.~E.~Brouwer}: Geodetic graphs of diameter two, Geom.
Dedicata 25 (1988), 527-533.

\bibitem{besa-91}
{\em S. L. Bezrukov, A. Sali}: On superspherical graphs. Sets,
graphs and numbers, Colloq. Math. Soc. J\'{a}nos Bolyai 60 (1991)
89-95.

\bibitem{blum-38}
{\em L. M. Blumenthal}: Distance geometries, University of Missouri
Studies vol. 13 (1938) no. 2.

\bibitem{bls-99} A.~Brandst\"{a}dt, V.~B.~Le and J.~P.~Spinrad, Graphs classes:
A survey, SIAM, Philadelphia, 1999.

\bibitem{halsted-902}
{\em Halsted, George Bruce}: The betweenness assumptions, American
Mathematical Monthly 9 (1902), 98--101.

\bibitem{cald-71}
{\em J. Calder}: Some elementary properties of interval convexities.
J. London Math. Soc. {\em 3} (1971), 422--428.

\bibitem{cahmp-06}
 {\em Jos\'e C\'aceres, Carmen Hernando, Merc\`e Mora, Ignacio M. Pelayo, Mari\'a L. Puertas, Carlos Seara}:
On geodetic sets formed by boundary vertices, Discrete. Math. 306
(2006) 188--198.

\bibitem{cahmpc-08}
{\em Jos\'{e} C\'{a}ceres , Carmen Hernando , Merc\`{e} Mora ,
Ignacio M. Pelayo , Mar\'{i}a L. Puertas , Carlos Seara}:
Geodeticity of the contour of chordal graphs, Disc. App. Math., 156
(7),(2008), 1132--1142.

\bibitem{chjo-98}
{\em M. Changat, J. Mathew}:  Interval monotone graphs:
minimal path convexity. Proc. of the conf. on graph connections
(R.Balakrishnan, H.M.Mulder and A.Vijayakumar eds.),New Delhi,
(1999), 87--90.

\bibitem{chjo-99}
{\em M. Changat, J. Mathew}: On Triangle path convexity in
graphs, Discrete Math. {\em 206} (1999) 91--95.

\bibitem{chjo-04}
{\em M. Changat, J.Mathew}: Induced path transit function, monotone
and Peano axioms. Discrete Math. 286 (2004), 185 –-194.

\bibitem{chjo-08}
{\em M. Changat, J. Mathew}: A characterization of $J$-monotone
graphs, In: Convexity in Discrete Structures (M.~Changat, S.~Klav\v
zar,  H.M.~Mulder, A.~Vijayakumar, eds.), Lecture Notes Ser. 5,
Ramanujan Math. Soc. (2008) 47--55.

\bibitem{chjomu-03}
{\em M.Changat, J.Mathew, H.M.Mulder}: Induced path transit function,
betweenness and monotonicity, Elect. Notes of Disc. Math., 15 (2003)

\bibitem{chjomu-ip}
{\em M.Changat, J.Mathew, H.M.Mulder}: Induced path function,
betweenness and monotonicity (revised version submitted to Disc.
App. Math).

\bibitem{chmusi-05}
{\em M. Changat, H. M. Mulder, G.Sierksma}: Convexities related to
path properties on graphs Disc. Math.,290, 2005, 117-131.

\bibitem{chklmu-01}
{\em M. Changat, S. Klav\`zar, H.M. Mulder}: The All-Paths Transit
Function of a Graph, Czech. Math. J. 51 (126) (2001), 439–448.

\bibitem{chergazh-03}
{\em G. Chartrand, D. Erwin, G. L. Johns, P. Zhang}: Boundary
vertices in graphs. (English) Disc. Math. 263, (1-3), (2003),
25--34.

\bibitem{cheszh-04}
{\em G. Chartrand, H. Escuadro, P. Zhang}: Extremal Problems on Distances in Graphs.
Cong. Numerantum 167 (2004) 133--147. Zbl 1064.05048

\bibitem{cheszh-05}
{\em G. Chartrand, H. Escuadro, P. Zhang}: Detour Distance in Graphs. JCMCC {\em 53}
 (2005) 75--94.  Zbl 1074.05029

 \bibitem{chgati-93}
{\em G. Chartrand, G.L.Johns,  S. Tian}: Detour distance in graphs.
(English) Gimbel, John (ed.) et al., Quo vadis, graph theory? A
source book for challenges and directions. Amsterdam: North-Holland.
Ann. Disc. Math., 55, (1993), 127--136.

\bibitem{chjozh-03}
{\em G. Chartrand, G.L. Johns, P. Zhang}: The Detour Number of a Graph.
Util.Math. 64 (2003) 97--113. Zbl 1033.05032

\bibitem{chjozh-04}
{\em G. Chartrand, G.L. Johns, P. Zhang}: On the Detour Number
and Geodetic Number of a Graph. Ars. Combinatoria, 72 (2004) 3--15.
Zbl 1073.05022

\bibitem{survey-02}
{\em G.~Chartrand, E.~M.~Palmer, P.~Zhang}: The geodetic number of a graph: a survey,
 Congr. Numer. 156 (2002) 37-58.

\bibitem{chzh02}
 {\em G.~Chartrand, P.~Zhang}: The Steiner Number of a Graph.
Disc. Math. 242 (2002) 41-54.

\bibitem{chzh-04}
{\em G. Chartrand, P. Zhang}: Distance in graphs - taking the long
view. (English) AKCE Int. J. Graphs Comb. 1, 1(2004), 1-13.

\bibitem{chav-09}
{\em Va\v{s}ek Chv\`{a}tal}: Antimatroids, betweenness, convexity,
in: William Cook, L\`{a}szl\`{o} Lov\`{a}sz, Jens Vygen (Editors),
Research Trends in Combinatorial Optimization, Springer, Berlin
2009, pp. 57 -- 64.

%\bibitem{chep-86}
%{\em V.D.Chepoi}: d-convex sets in graphs,Ph.D.dissertation, Moldova
%State University, Kishinev. (1986)(Russian)

\bibitem{jac-36}
{\em J. A. Clarkson}: Uniformly convex spaces, Trans. Amer. Math.
Soc. vol. 40 (1936) pp.396--414.

\bibitem{deza-06}
{\em M.M. Deza, E. Deza}: Dictionary of distances, Elsevier,(2006).

%\bibitem{du-87} P.~Duchet: Convexity in combinatorial structures.
%{\it{Rend.Circ.Mat Palermo (2) Suppl.}} 14 (1987), 261--293.

\bibitem{duch-88}{\em P. Duchet}: Convex sets in graphs II. Minimal path
convexity. J. Combin. Theory Ser. B. {\em 44} (1988), 307--316.

%\bibitem{dume-84}
%{\em P. Duchet and H. Meyniel}: Ensemble convexes dans les graphes
%I. Europ. J. Combin. {\em 4} ( 1983), 127--132.

\bibitem{eo}
{\em L.~Eroh, O.~R.~Oellermann}: Geodetic and Steiner geodetic sets in
3-Steiner distance hereditary graphs, Discrete Math., in press.

\bibitem{idau-06}
{\em Ivo D{\"{u}}ntsch and Alasdair Urquhart}: Betweenness and Comparability Obtained from Binary Relations, In Renate Schmidt, editor, Proceedings of the 9th  International Conference on Relational Methods in Computer Science and the 4th International Workshop on Applications of Kleene Algebra, volume 4136 of Lecture Notes in Computer Science, pages 148-161. Springer-Verlag, Heidelberg, 2006.

%\bibitem{faja-86}
%{\em M. Farber and R.E. Jamison}: Convexity in graphs and
%hypergraphs. SIAM J. Algebraic Discrete Methods {\em 7} (1986),
%433--444.

%\bibitem{faba-87}
%{\em M. Farber}: Bridged graphs and geodesic convexity. Discrete
%Math. {\em 66} (1987), 249--257.

%\bibitem{faja-87}
%{\em M.Farber, R.E. Jamison}: On local convexity in graphs,
%Discrete .Math {\em 66} (1987), 231-247.

\bibitem{freeman-77}
{\em L. C. Freeman}: A set of measures of centrality based on
betweenness, Sociometry 40 (1977), 35.

\bibitem{fbf-01}{\em M. Frick, F. Bullock}: Detour chromatic numbers. Discuss.
Math. Graph Theory 21 (2001). Zbl 1002.05021

\bibitem{gago}
{\em S. Gago}: The betweenness centrality of a graph,\\
http://hdl.handle.net/2117/972

\bibitem{gilipa-02}
{\em Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani}:
Orthogonal 3D Shapes of Theta Graphs, Lecture Notes in Computer
Science (G. Goos, J. Hartmanis, and J. van Leeuwen editors,), 2528
(2002) 273-292.

%\bibitem{gliv}
%{\em V. Glivenko}: G\'eom\'etrie des syst\'emes de choses norm\'es,
%Amer. J. Math. vol. 58 (1936) 799-828.
\bibitem{hall-35}
{\em P. Hall}: On representation of subsets, J. Lon. Mat. Sc. 10
(1935), 26--30.

\bibitem{hno}
{\em M.~A.~Henning, M.~H.~Nielsen, O.~R.~Oellermann}: Local Steiner convexity,
Europ. J. Combin, in press.

\bibitem{hjmps05}
{\em C.~Hernando, T.~Jiang, M.~Mora, I.M.~Pelayo, C.~Seara}: On
the Steiner, geodetic and hull numbers of graphs, Discrete Math. 293
(2005) 139-154.

\bibitem{hilb-89}
{\em D. Hilbert}: Grundlagen der Geometrie, 1899.

\bibitem{hrw92}
{\em F.~Hwang, D.~Richards, P.~Winter}: The Steiner tree
problem, Ann. Disc. Math. 53, North Holland, Amsterdam, 1992.

%\bibitem{jawa-82}
%{\em R.E. Jamison, Waldner}: A perspective on abstract convexity:
%classifying  alignments by varieties, in convexity and related
%combinatorial geometry. Proceedings of 2nd Oklahoma conf.(D.C.Kay
%and M. Breen Eds) New York, (1982), 113--150.

\bibitem{jarmila-83}
{\em J. Hedl\'ikov\'a}: Ternary spaces, media, and Chebyshev sets,
Czech. Math. J. 33 (1983), no. 3,  373-–389.

\bibitem{jarmila-96}
{\em J. Hedl\'ikov\'a, Tibor Katri\~{n}\'ak}: Lattice Betweenness
Relation and Generalization of Konig's Lemma, Math. Slovaca, 46
(1996), No. 4, 343--354.

%\bibitem{jys-99}
%{\em J. \.Y Simko}:Metrizable and \textrm{R}-­Metrizable Betweenness
%Spaces,Proc. of Amer. Math. Soc., Vol. 127(2), 1999, 323--325.

\bibitem{king-64}
{\em J. F. C. Kingman}: Metrics for Wald spaces, J. London Math.
Soc, 39 (1964), 129--130.

%\bibitem{klmu-99}
%{\em S. Klav\v zar, H.M. Mulder}: Median graphs:
%characterizations, location theory and related structures. J.
%Combin. Math. Combin. Comp., to appear

\bibitem{ko-93}
{\em J.~H.~Koolen}: On uniformly geodetic graphs, Graphs Combin. 9 (1993),
325--333.

\bibitem{kuoe98}
{\em E.~Kubicka, G.~Kubicki, O.~R.~Oellermann}: Steiner intervals
in graphs, Disc. Math. 81 (1998) 181--190.

\bibitem{mac-59}
{\em S. MacLane}: Metric postulates for plane geometry, American
Mathematical Monthly 66 (1959), 543--555.

\bibitem{menzla}
{\em R. Mendris and P. Zlato\"{Y}s}: Axiomatization and undecidability
results for metrizable between­ ness relations, Proc. Amer. Math.
Soc. 123 (1995), 873--882.

\bibitem{menger-42}
{\em K. Menger}: Statistical metrics, Proc. Nat. Acad. Sci. U.S.A.,
28 (1942), 535--537.

\bibitem{mol}
{\em M.~Mollard}: Interval-regularity does not lead to interval
monotonicity, Disc. Math. 118 (1993) 233--237.

\bibitem{mr-07}
{\em A.~Moss, Y.~Rabani}: Approximation algorithms for constrained
node weighted Steiner tree problems, SIAM J. Comput. 37 (2007),
460--481.

\bibitem{momu-02}
{\em M.A. Morgana, H.M. Mulder}: Induced path convexity, betweenness and
svelte graphs, Discrete Math. 254, (2002), 349--370.

\bibitem{rmbs}
{\em R. Moynihan and B. Schweizer}, Betweenness Relations in
Probabilistic Metric Spaces,Pacific J. Math.,Vol. 81, No.1,(1979),
175--196.

%\bibitem{muld-78}
%{\em H.M. Mulder}: The Structure of Median graphs. Discrete. Math.
%{\em 24}, (1978), 197--204.

\bibitem{muld-80}
{\em H.M.~Mulder}: The Interval Function of a Graph.
Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam,
(1980).

\bibitem{muld-08}
{\em H. M. Mulder}: Transit functions on graphs (and posets), In: Convexity in Discrete Structures (M.~Changat, S.~Klav\v zar,  H.M.~Mulder, A.~Vijayakumar, eds.), Lecture Notes Ser. 5,
Ramanujan Math. Soc. (2008)
133–-148.

%\bibitem{mush-79}
%{\em H.M. Mulder, Schrijver}: Median graphs and helly
%hypergraphs. Discrete. Math. {\em 25}, (1979), 41--50.

%\bibitem{mulat}
%{\em H.M. Mulder, Schrijver}: n cubes and Median graphs. J.graph
%theory {\em 4}, (1980), 107--110.

\bibitem{mune-09}
{\em H.M. Mulder,  L. Nebesk\'{y}}: Axiomatic characterization of
the interval function of a graph. Europ. J. Combin,
doi:10.1016/j.ejc.2008.09.007

\bibitem{nebe-94}
{\em L. Nebesk\'{y}}:Characterization of the set of all
shortest paths in a connected graph. Math. Boh.,119,(1994),15--20.

\bibitem{nebe-98}
{\em L. Nebesk\'{y}}: Characterization of the interval function of a
connected graph Czech. Math. Journal. 44,(1994),173--178.

\bibitem{nebe-01a}
{\em L. Nebes\'ky}: A characterization of the interval function of a
(finite or infinite) connected graph, Czechoslovak Math. J. 51 (126)
(2001), 635--642.

\bibitem{nebe-01b}
{\em L. Nebes\'ky}: The interval function of a connected graph and a
characterization of geodetic graph, Math. Bohemica 126 (2001),
247–-254.

\bibitem{ne-02}
{\em L.~Nebesk\'y}: New proof of a characterization of geodetic graphs,
Czechoslovak Math. J. 52 (2002) 33--39.

\bibitem{nebe-04}
{\em L. Nebes\'ky}: Intervals and steps in a connected graph,
Disc. Math. 286 (2004), 151 – 156, doi:10.1016/disc.2003.11.056

\bibitem{nebe-07}
{\em L. Nebes\'ky}: The interval function of a
connected graph and road systems, Discrete Math. 307 (2007), 2067 –
2073., doi:10.1016/disc.2005.12.051

\bibitem{niem-88}
{\em J. Nieminen}: Join Space graphs, J. Geom. 33 (1988).

\bibitem{oell90}
{\em O.~R.~Oellermann}: Steiner numbers in graphs, Quaestiones
Math. 13 (1990) 159--164.

\bibitem{oelpue07}
{\em O.~R.~Oellermann, M.~L.~Puertas}: Steiner intervals and
Steiner geodetic numbers in distance-hereditary graphs, Discrete
Math. 307 (2007) 88--96.

\bibitem{Pelayo}
{\em I.~Pelayo}: Comment on: ``The Steiner number of a graph''  by
G. Chartrand and P. Zhang [Discrete Math. 242 (2002), no. 1-3,
41--54], Discrete Math. 280 (2004) 259--263.

\bibitem{epmf-42}
{\em E. Pitcher and M.F. Smiley}: Transitivities of Betweenness,
Trans.Am.Math. Soc., 52, (1942), 95-–114.

\bibitem{pl-84}
{\em  J.~Plesn\'ik}: A construction of geodetic graphs based on pulling subgraphs homeomorphic
to complete graphs, J. Combin. Theory Ser. B 36 (1984) 284--297.

\bibitem{prjn}
{\em W. Prenowitz, J. Jantosciak}: Geometris and Join spaces, J.
Reine Angew. Math. 257, (1972), 100--128.

\bibitem{rohd-64}
{\em F. Rhodes}: Convexity in Wald's statistical metric spaces, J.
London Math. Soc, 39 (1964), 117--128.

\bibitem{samp-96}
{\em E. Sampathkumar}: B systems. Proc. National workshop on graph
theory and its applications, Manonmaniam Sundaranar University,
Tirunelveli. (1996), 173--185.

\bibitem{samp-84}
{\em E. Sampathkumar}: Convex sets in graphs. Indian J. Pure Appl.
Math. 15 (1984), 1065–1071.

\bibitem{sher-70}
{\em H. Sherwood}: Betweenness in probabilistic metric spaces, Rev.
Roum. Math. Pures et Appl., 15 (1970), 1061--1068.

%\bibitem{mfwr-43}
%{\em M. F. Smiley, W. R. Transue}: Applications Of
%Transitivities Of Betweenness In Lattice Theory, Trans.Am.Math.
%Soc., 52, (1943)280-–287.

\bibitem{mfs-43}
{\em M. F. Smiley}: A Comparison of Algebraic, Metric, And Lattice
Betweenness, Trans.Am.Math. Soc., 52, (1943), 246-–252.


\bibitem{ehrk-17}
{\em E.V. Huntington, J. Robert Kline}: Set of independent
postulates for betweenness. Trans. Am. Math. Soc., 18, (1917),
301-–325.

\bibitem{shol-54}
{\em M. Sholander}: Medians and Betweenness. Proc. Am. Math. Soc.,5,
(1954), 801--807.

\bibitem{shol-52} {\em M. Sholander}: Trees,
lattices, order and betweenness. Proc. Am. Math. Soc., 3, (1952),
369–-381.

\bibitem{dan}
{\em D. A. Simovici}: Betweenness, Metrics and Entropies in Lattices, 38th IEEE International Symposium on Multiple-Valued Logic (ISMVL 2008),26--31.

\bibitem{stwa-98}
{\em P.F. Stadler, G.P. Wagner}: The Algebraic Theory of Recombination Spaces, Evol.Comp.
 5 (1998) 241--275.

\bibitem{stst-03}
{\em  P.F. Stadler, C.R. Stephens}: Landscapes and Effective Fitness,
Comments Theor. Biol. 8 (2003) 389--431.

\bibitem{st-74}
{\em J.~G.~Stemple}: Geodetic graphs of diameter two, J. Combin. Theory Ser. B 17 (1974) 266-280.

\bibitem{vel-93}
{\em M.L.J. Van de Vel}: Theory of Convex Structures.
 North Holland, Amsterdam, 1993.

\bibitem{wald-43}
{\em A. Wald}: On a statistical generalization of metric spaces,
Proc Nat. Acad. Sci., U.S.A., 29 (1943), 196-199.

\bibitem{wast-99}
{\em  G.P. Wagner, P.F. Stadler}: Complex Adaptations and the Structure of Recombination Spaces,
In: C.L. Nehaniv, M. Ito (eds.) ``Algebraic Engineering'' World
Scientific (1999) 96--115. (Proceedings of the Conference on
Semi-Groups and Algebraic Engineering, University of Aizu, Japan)

\bibitem{wast-03}
{\em  G.P. Wagner, P.F. Stadler}: Quasi-Independence, Homology and the Unity of Type: A Topological
Theory of Characters, J. Theor. Biol. 220 (2003)
505--527.

%\bibitem{wilcox}
%{\em L. R. Wilcox, M. F. Smiley}:
%Metric lattices, Ann. of Math. (2) vol. 40 (1939) pp. 309--327.

\bibitem{west}
{\em D.B. West}: Introduction to Graph Theory 2nd Edn.(2003) Prentice-Hall
of India, New Delhi.


\end{thebibliography}

\addcontentsline{toc}{chapter}{Index}
\printindex

\end{document}

\section{Weakly-modular graphs}


\chapter{The path transit function $I_1$ and betweenness axioms}
\chapter{The longest path trnaist function and its betweennes}
\chapter{Detour and some boundary related results}
\chapter{Steiner transit function and the betweenness axioms}
\chapter{Conclusion}





The concept of betweenness in graphs was introduced by Mulder in
\cite{muld-08}, but he implicitly considered it already in his book
\cite{muld-80}. One of the starting points of his study were two
very strong properties that the geodesic interval $I$ enjoys.
Namely, (i) if $x$ is between $u$ and $v$ (i.e. $x\in I(u,v)$) and
$x\neq u$, then $u$ is not between $x$ and $v$, and, (ii) if $x$ is
between $u$ and $v$, and $y$ is between $u$ and $x$, then $y$ is in
between $u$ and $v$. Properties (i) and (ii) are usually denoted by
$(b1)$ and $(b2)$, respectively, and together they form
\emph{betweenness axioms} as defined in \cite{muld-08}. The
interpretation of the betweenness properties in this sense was first
studied by Mulder and Morgana \cite{momu-97}, where it was also
proved that the induced path interval $J$ is a betweenness if and
only if $G$ is a house, hole, domino-free graph. A related property
(not always satisfied by $I$) is that if $x$ and $y$ are between $u$
and $v$, and $z$ is between $x$ and $y$, then $z$ is between $u$ and
$v$. This property is known as the \emph{monotone
axiom}, which is again introduced formally in \cite{muld-08}. (In \cite%
{vel-93}, van de Vel uses the term monotone law for what we call the
$(b2)$ axiom.) The graphs in which the monotone axiom is always
satisfied are known as interval monotone graphs which were also
introduced in \cite{muld-80}, see also \cite{besa-91,mol}. Clearly
the monotone axiom always implies $(b2)$, but the converse need not
hold and the characterization of interval monotone graphs is still
an open problem. Betweenness in discrete structures other than
graphs has been studied much earlier, for example see
\cite{shol-54}.
