错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Walk Domination and HHD-Free Graphs

  • Silvia B. Tondato

摘要

HHD-free is the class of graphs which contain no house, hole, or domino as induced subgraph. It is known that HHD-free graphs can be characterized via LexBFS-ordering and via \(m^3\) m 3 -convexity. In this paper we present new characterizations of HHD-free via domination of paths and walks. To achieve this, in particular we concentrate our attention on \(m_3\) m 3 path, i.e, an induced path of length at least 3 between two non-adjacent vertices in a graph G. We show that the domination between induced paths, paths and walks versus \(m_3\) m 3 paths, gives rise to characterization of HHD-free. We also characterize the class of graphs in which every \(m_3\) m 3 path dominates every path, induced path, walk, and \(m_3\) m 3 path, respectively.