Stars in Forbidden Triples Generating a Finite Set of 4-Connected Graphs
摘要
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.