A Note on Path Domination

Abstract

We study domination between different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks). We succeeded in characterizing those graphs in which every uv-walk of one particular kind dominates every uv-walk of other specific kind. We thereby obtained new characterizations of standard graph classes like chordal, interval and superfragile graphs.

Keywords

• domination
• paths
• geodesics
• chordal graphs
• interval graphs