Forbidden trees with diameter six for 3-connected graphs

For a family \(\mathcal F\) of graphs, a graph \(G\) is said to be \(\mathcal F\)-free if \(G\) contains no member of \(\mathcal F\) as an induced subgraph. We let \(\mathcal G_{3}(\mathcal F)\) be the family of \(3\)-connected \(\mathcal F\) -free graphs. Let \(P_{n}\) and \(C_{n}\) denote the path and the cycle of order \(n\), respectively. Let \(T_{0}\) be the tree of order nine obtained by joining a pendant edge to the central vertex of \(P_{7}\). Let \(T_{1}\) and \(T_{2}\) be the trees of order ten obtained from \(T_{0}\) by joining a new vertex to a vertex of \(P_{7}\) adjacent to an endvertex, and to a vertex of \(P_{7}\) adjacent to the central vertex, respectively. We show that \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{1}\})\) and \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{2}\})\) are finite families.

Authors

Publication Details

Journal
Ars Combinatoria
Published
2025-09-30
DOI
https://doi.org/10.61091/ars164-01
Primary Topic
Graph Labeling and Dimension Problems
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Forbidden trees with diameter six for 3-connected graphs

Yoshimi Egawa
Ars Combinatoria
Graph Labeling and Dimension Problems
article

Forbidden trees with diameter six for 3-connected graphs

Yoshimi Egawa
article en

Abstract

For a family \(\mathcal F\) of graphs, a graph \(G\) is said to be \(\mathcal F\)-free if \(G\) contains no member of \(\mathcal F\) as an induced subgraph. We let \(\mathcal G_{3}(\mathcal F)\) be the family of \(3\)-connected \(\mathcal F\) -free graphs. Let \(P_{n}\) and \(C_{n}\) denote the path and the cycle of order \(n\), respectively. Let \(T_{0}\) be the tree of order nine obtained by joining a pendant edge to the central vertex of \(P_{7}\). Let \(T_{1}\) and \(T_{2}\) be the trees of order ten obtained from \(T_{0}\) by joining a new vertex to a vertex of \(P_{7}\) adjacent to an endvertex, and to a vertex of \(P_{7}\) adjacent to the central vertex, respectively. We show that \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{1}\})\) and \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{2}\})\) are finite families.

Ars CombinatoriaVol. 164
Openalex Percentile: Top 72%
Graph Labeling and Dimension Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.