Premium
Graphs without isometric rays and invariant subgraph properties, I
Author(s) -
Polat Norbert
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199802)27:2<99::aid-jgt5>3.0.co;2-a
Subject(s) - mathematics , combinatorics , invariant (physics) , induced subgraph isomorphism problem , isometric exercise , discrete mathematics , graph , line graph , biology , voltage graph , physiology , mathematical physics
A ray of a graph G is isometric if every path in R is a shortest path in G . A vertex x of G geodesically dominates a subset A of V ( G ) if, for every finite S ⊆ V ( G − x ), there exists an element a of A − { x } such that the interval (set of vertices of all shortest paths) between x and a is disjoint from S . A set A ⊆ V ( G ) is geodesically closed if it contains all vertices which geodesically dominate A . These geodesically closed sets define a topology, called the geodesic topology , on V ( G ). We prove that a connected graph G has no isometric rays if and only if the set V ( G ) endowed with the geodesic topology is compact, or equivalently if and only if the vertex set of every ray in G is geodesically dominated. We prove different invariant subgraph properties for graphs containing no isometric rays. In particular we show that every self‐contraction (map which preserves or contracts the edges) of a chordal graph G stabilizes a non‐empty finite simplex (complete graph) if and only if G is connected and contains no isometric rays and no infinite simplices. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 99–109, 1998