Header menu link for other important links
X
Interval function, induced path function, (claw, paw)-free graphs and axiomatic characterizations
Manoj Changat, Hossein Nezhad Ferdoos,
Published in Elsevier BV
2020
Volume: 280
   
Pages: 53 - 62
Abstract
The axiomatic study on the interval function, induced path function and all-paths function of a connected graph is a well-known area in metric graph theory and related areas. In this paper, we introduce the following new axiom: (cp) v∈R(u,w) and v∈R(u,x)⇒w∈R(v,x) or x∈R(v,w), for all distinct u,v,w,x∈V.We present characterizations of (claw, paw)-free graphs using axiom (cp) on the standard path transit functions on graphs, namely the interval function, the induced path function and the all-paths function. We study the underlying graphs of the transit functions which are (claw, paw)-free and Hamiltonian. We present an axiomatic characterization of the interval function on (claw, paw)-free graphs. Furthermore, we obtain an axiomatic characterization of the induced path function on a subclass of (claw, paw)-free graphs.
About the journal
JournalData powered by TypesetDiscrete Applied Mathematics
PublisherData powered by TypesetElsevier BV
ISSN0166218X
Open AccessNo