Scholarlink

We denote by \(\mathscr {P}(G)\) the graph whose vertices are the induced non-trivial paths in G, and where two vertices (induced paths) are adjacent if and only if they share a common edge. Set \(\mathscr {P}^0(G)=G\) , and \(\mathscr {P}^k(G)=\mathscr {P}(\mathscr {P}^{k-1}(G))\) for integers \(k\ge 1\) . Furthermore, \(\mathscr {P}(G)=\emptyset \) if G has no non-trivial induced paths. If we consider the sequence \(\langle \mathscr {P}^k(G)\rangle _{k=0}^\infty \) , it can happen that (a) \(\mathscr {P}^k(G)=\emptyset \) for some \(k>0\) , or (b) the order of \(\mathscr {P}^k(G)\) increases without bound, or (c) there are only a finite number of elements of the sequence up to isomorphism. A characterization of the graphs in each of these three cases is given in this paper.

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

The Edge-Intersection Graph of Induced Paths in a Graph

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Severino V. Gervacio

摘要

We denote by \(\mathscr {P}(G)\) the graph whose vertices are the induced non-trivial paths in G, and where two vertices (induced paths) are adjacent if and only if they share a common edge. Set \(\mathscr {P}^0(G)=G\) , and \(\mathscr {P}^k(G)=\mathscr {P}(\mathscr {P}^{k-1}(G))\) for integers \(k\ge 1\) . Furthermore, \(\mathscr {P}(G)=\emptyset \) if G has no non-trivial induced paths. If we consider the sequence \(\langle \mathscr {P}^k(G)\rangle _{k=0}^\infty \) , it can happen that (a) \(\mathscr {P}^k(G)=\emptyset \) for some \(k>0\) , or (b) the order of \(\mathscr {P}^k(G)\) increases without bound, or (c) there are only a finite number of elements of the sequence up to isomorphism. A characterization of the graphs in each of these three cases is given in this paper.