Header menu link for other important links
X
Axiomatic characterization of claw and paw-free graphs using graph transit functions
, Manoj Changat, Ferdoos Hossein Nezhad
Published in Springer Verlag
2016
Volume: 9602
   
Pages: 115 - 125
Abstract
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.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo
Concepts (11)
  •  related image
    Graphic methods
  •  related image
    Hamiltonians
  •  related image
    2-CONNECTED GRAPHS
  •  related image
    AXIOMATIC APPROACH
  •  related image
    AXIOMATIC CHARACTERIZATION
  •  related image
    FREE GRAPHS
  •  related image
    HAMILTONIAN GRAPH
  •  related image
    INDUCED PATHS
  •  related image
    Interval functions
  •  related image
    TRANSIT FUNCTIONS
  •  related image
    Graph theory