In 1952 Sholander formulated an axiomatic characterization of the interval function of a tree with a partial proof. In 2011 Chvátal et al. gave a completion of this proof. In this paper we present a characterization of the interval function of a block graph using axioms on an arbitrary transit function R. From this we deduce two new characterizations of the interval function of a tree. © 2015 Elsevier B.V.All rights reserved.

N. Narayanan

Department of Mathematics

Kannan Balakrishnan

Manoj Changat

Anandavally K. Lakshmikuttyamma

Joseph Mathew

Henry Martyn Mulder

Prasanth G. Narasimha-Shenoi

Fulltext

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Discrete Mathematics

The axiomatic approach with the interval function and induced path transit function of a connected graph is an interesting topic in metric and related graph theory. In this paper, we introduce a new axiom: (bp) for any x, y, z ∈ V, R(x, y) = {x, y} ⇒ y ∈ R(x, z) or x ∈ R(y, z). We study axiom (bp) on the interval function and the induced path transit function of a connected, simple and finite graph. We present axiomatic characterizations of the interval function of bipartite graphs and complete bipartite graphs. Further, we present an axiomatic characterization of the induced path transit function of a tree or a 4-cycle. © Springer International Publishing AG 2017.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Axiomatic characterization of the interval function of a bipartite graph

The axiomatic approach with the interval function, induced path transit function and all-paths transit function of a connected graph form a well studied area in metric and related graph theory. In this paper we introduce the first order axiom: (cp) For any pairwise distinct vertices a, b, c, d ∈ V b ∈ R(a, c) and b ∈ R(a, d) ⇒ c ∈ R(b, d) or d ∈ R(b, c). We study this new axiom on the interval function, induced path transit function and all-paths transit function of a connected simple and finite graph. We present characterizations of claw and paw-free graphs using this axiom on standard path transit functions on graphs, namely the interval function, induced path transit function and the all-paths transit function. The family of 2-connected graphs for which the axiom (cp) is satisfied on the interval function and the induced path transit function are Hamiltonian. Additionally, we study arbitrary transit functions whose underlying graphs are Hamiltonian. © Springer International Publishing Switzerland 2016.

Journal	Data powered by TypesetDiscrete Mathematics
Publisher	Data powered by TypesetElsevier
ISSN	0012365X
Open Access	Yes