Let \( \mathcal {G} \) and \( \mathcal {G}_{4}(\mathcal {F}) \) denote the collection of all connected graphs having at least three vertices and the collection of 4-connected \( \mathcal {F}\) -free graphs, respectively, where \( \mathcal {F} \subseteq \mathcal {G} \) . A graph G is said to be \( \mathcal {F}\) -free if for every \( F \in \mathcal {F} \) , G does not contain F as an induced subgraph. The members of \( \mathcal {F}\) are called forbidden subgraphs and the set \( \mathcal {F}\) with order three is called a forbidden triple. In this paper, we determine forbidden triples \( \mathcal {F}\) for which \( \mathcal {G}_{4}(\mathcal {F}) \) is finite. Specifically, this paper proves that if \( \mathcal {G}_{4}(\left\{ K_3,K_{1,m}, T \right\} ) \) is finite, where \( m \ge 5 \) , then T is either a path of order at least four, or a caterpillar having maximum degree at most four such that no degree four vertex is adjacent to a vertex of degree three or higher, and no three vertices of degree three are contiguously adjacent. Moreover, this paper proves that \( \mathcal {G}_4({\left\{ K_{n}, K_{1,m}, T \right\} }) \) is finite, where \( n \ge 4 \) and \( m \ge 5 \) if and only if T is a path. Also, it will be shown that if \( \mathcal {G}_{4}(\left\{ K_n,K_{1,m}, T \right\} ) \) is finite, where \( 3 \le m \le 4 \) and \( n \ge 4 \) , then T is a cactus such that all cycles of T are triangles and whose block-cutvertex graph is a path.

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

Stars in Forbidden Triples Generating a Finite Set of 4-Connected Graphs

  • Orville Buelban,
  • Agnes D. Garciano,
  • Reginaldo M. Marcelo,
  • Ayaka Mori,
  • Shunsuke Nakamura

摘要

Let \( \mathcal {G} \) and \( \mathcal {G}_{4}(\mathcal {F}) \) denote the collection of all connected graphs having at least three vertices and the collection of 4-connected \( \mathcal {F}\) -free graphs, respectively, where \( \mathcal {F} \subseteq \mathcal {G} \) . A graph G is said to be \( \mathcal {F}\) -free if for every \( F \in \mathcal {F} \) , G does not contain F as an induced subgraph. The members of \( \mathcal {F}\) are called forbidden subgraphs and the set \( \mathcal {F}\) with order three is called a forbidden triple. In this paper, we determine forbidden triples \( \mathcal {F}\) for which \( \mathcal {G}_{4}(\mathcal {F}) \) is finite. Specifically, this paper proves that if \( \mathcal {G}_{4}(\left\{ K_3,K_{1,m}, T \right\} ) \) is finite, where \( m \ge 5 \) , then T is either a path of order at least four, or a caterpillar having maximum degree at most four such that no degree four vertex is adjacent to a vertex of degree three or higher, and no three vertices of degree three are contiguously adjacent. Moreover, this paper proves that \( \mathcal {G}_4({\left\{ K_{n}, K_{1,m}, T \right\} }) \) is finite, where \( n \ge 4 \) and \( m \ge 5 \) if and only if T is a path. Also, it will be shown that if \( \mathcal {G}_{4}(\left\{ K_n,K_{1,m}, T \right\} ) \) is finite, where \( 3 \le m \le 4 \) and \( n \ge 4 \) , then T is a cactus such that all cycles of T are triangles and whose block-cutvertex graph is a path.