Electronic Journal of Graph Theory and Applications 13 .
, 1Ae17 Stars in forbidden triples generating a finite set of graphs with minimum degree four Takafumi Kotani Department of Applied Mathematics Tokyo University of Science 1-3 Kagurazaka.
Shinjuku,Tokyo 162-8601.
Japan 1423703@ed.
Abstract For a family H of graphs, a graph G is said to be H-free if G contains no member of H as a induced subgraph.
Let GE4 (H) denote the family of connected H-free graphs having minimum degree at least 4.
In this paper, we characterize the families H of connected graphs with |H| = 3 such that H contains a star and GE4 (H) is a finite family, except for the case where {K4 .
K1,n } OI H with 3 O n O 4.
Keywords: forbidden subgraph, forbidden triple Mathematics Subject Classification: 05C75 DOI: 10.
5614/ejgta.
Introduction In this paper, we consider only finite undirected simple graphs.
Let G be a graph.
Let V (G) and E(G) denote the vertex set and the edge set of G, respectively.
For a vertex u OO V (G), let NG .
and dG .
denote the neighborhood and the degree of u, respectively.
thus NG .
= .
OO V (G) | uv OO E(G)} and dG .
= |NG .
We let (G) and OI(G) denote the minimum degree and the maximum degree of G, respectively.
For a subset U of V (G), let NG (U ) = uOOU NG .
, and let G[U ] denote the subgraph of G induced by U .
For two subset U.
U A of V (G) with U O U A = OI.
Received: 17 September 2023.
Revised: 9 December 2024.
Accepted: 18 December 2024.
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani E(U.
U A ) := .
y OO E(G) | x OO U, y OO U A }.
For u, v OO V (G), let distG .
, .
denote the length of a shortest u-v path of G.
Let diam(G) denote the maximum of distG .
, .
among all pairs u, v OO V (G).
For two positive integers s1 and s2 , the Ramsey number R.
1 , s2 ) is the minimum positive integer R such that any graph of order at least R contains a clique of order s1 or an independent set of cardinality s2 .
For terms and symbols not defined in this paper, we refer the reader to .
For two graphs G and H, we write H O G if G contains an induced copy of H, and G is said to be H-f ree if H O G.
For a family H of graphs, a graph G is said to be H-f ree if G is H-free for every H OO H.
In this context, the members of H are called f orbidden subgraphs of G.
For an integer k Ou 1 and a family H of graphs, we let Gk .
GEk ) denote the set of all k-connected graphs .
connected graphs with minimum degree at least .
, and let Gk (H) .
GEk (H)) denote the set of all H-free graphs belonging to Gk .
GEk ), that is.
Gk (H) := {G | G is a k-connected H-free grap.
GEk (H) := {G | G is a connected H-free graph with minimum degree at least .
The main aim of this paper is to characterize the families H of connected graphs satisfying the condition that |H| = 3 and GE4 (H) is a finite family, .
in the case where H contains a star.
If a complete graph of order at most 2 belongs to H, then GE4 (H) is clearly empty.
Thus, in the rest of this paper, we consider the case where every graph belongs to H has order at least 3.
Our motivation derives from characterization of families H of connected graphs satisfying the condition that Gk (H) is a finite family.
If a family H satisfies .
, then for any property P on graphs, although the proposition that all k-connected H-free graphs satisfy P with finite exceptions .
holds, the proposition gives no information about P .
Thus, it is important to identify families H satisfying .
in advance.
Having such a motivation.
Fujisawa.
Plummer and Saito .
started a study of families H satisfying .
, and determined the families H satisfying .
for the case where 1 O k O 6 and |H| O 2, and .
, |H|) = .
, .
In .
, 3, 4, .
, the research was continued by analyzing families H satisfying .
for the case where .
, |H|) = .
, .
, .
, .
In view of the fact that connectivity conditions can often be replaced by minimum degree condition in propositions like .
, it is natural to consider connected graphs with minimum degree at least k in place of k-connected graphs.
Thus, we consider the characterization of families H of connected graphs satisfying the condition that GEk (H) is a finite family.
In fact.
Egawa and M.
Furuya .
, .
characterized the families H of connected graphs satisfying condition .
, |H|) = .
, .
except for a special case.
Therefore, we consider the characterization of families H of connected graphs satisfying condition .
, |H|) = .
, .
, that is, characterization of the families H of connected graphs satisfying condition .
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Figure 1.
Graphs Y3 .
Y3O .
Z4 and Z4O Before describing several results, we define some graphs.
Let n be an integer with n > 2.
Let P = x1 x2 .
xn be the path of order n, and let y1 , y2 , z1 and z2 be four distinct vertices different from x1 , .
, xn .
Let Yn .
YnO .
Zn and ZnO denote the graphs defined by V (Yn ) = V (Zn ) = V (P ) O .
1 , y2 }.
V (YnO ) = V (ZnO ) = V (P ) O .
1 , y2 , z1 , z2 }.
E(Yn ) = E(P ) O .
1 y1 , x1 y2 }.
E(YnO ) = E(P ) O .
1 y1 , x1 y2 , xn z1 , xn z2 }.
E(Zn ) = E(Yn ) O .
1 y2 }, and E(ZnO ) = E(YnO ) O .
1 y2 , z1 z2 }.
ee Figure .
Let A1 .
A2 .
A3 and A4 be the graphs depicted in Figure 2.
We call vertices x and y in Figure 2 the f irst vertex and the last vertex of Ai .
= 1, 2, 3, .
, respectively.
Figure 2.
Graphs A1 .
A2 .
A3 and A4 For an integer s Ou 1, let Js be the family of the graphs obtained from s pairwise vertex-disjoint copies L1 , .
Ls of A1 .
A2 .
A3 or A4 by the following construction:
- Let x.
and y .
be two vertices of Li where x.
and y .
respectively correspond to x, y .
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Figure 3.
Graph belonging to J - For each integer i with 2 O i O s, we identify y .
Oe.
with x.
Let J := Ji .
ee Figure .
(Note that J can be expressed as the family of the graphs iOON obtained by combining with some graphs of the form Zt with t Ou 1.
Let G be a connected graph.
A vertex v of G is called a cutvertex if G Oe v is disconnected.
G has a cutvertex.
G is said to be separable.
otherwise, it is said to be nonseparable.
Note that K1 is a nonseparable graph.
A maximal nonseparable subgraph of G is called a block of G.
When G is separable, the block-cutvertex graph of G is defined to be the bipartite graph Z such that Z has as its partite sets the set of all cutvertices of G and the set of all blocks of G and, for a cutvertex v and a block B, v and B are adjacent in Z if and only if v is a vertex of B in G.
It is a well-known fact that the block-cutvertex graph of a connected graph is a tree.
Let Kl .
Km1 ,m2 .
Pn denote the complete graph of order l, the complete bipartite graph with partite sets having cardinalities m1 and m2 , and the path of order n, respectively.
A complete bipartite graph of the form K1,m with m Ou 1 is called a star.
A caterpillar is a tree for which the removal of all endvertices leaves a path.
A cactus is a connected graph every block of which is a complete graph of order two or a cycle.
We shall use the following sets in the discussion that will follow.
Let T0 be the set of trees, are none of K1,2 .
K1,3 and K1,4 , having order greater than or equal to three and maximum degree at Note that T0 dose not contain a star.
Let T1 be the set of those caterpillars belongs to T0 in which the vertices of degree 4 and the vertices of degree 3 or higher are not adjacent, and no three vertices of degree 3 are contiguously adjacent.
Let T2 = {Pl .
Ym .
YnO | l Ou 4, m Ou 3, n Ou .
Let T0O be the set of those cacti T having order greater than or equal to four such that all cycle of T are triangles.
Let T1O be the set of those members of T0O whose block-cutvertex graph is a O Let T2O = {Pl .
Zm .
Z2n | l Ou 4, m Ou 2, n Ou .
We have T0O ON T1O ON T2O .
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Our main result is as follows.
Theorem 1.
Let l, n be integers with l Ou 3, n Ou 2, and let T be a connected graph of order at If GE4 ({Kl .
K1,n .
T }) is a finite family, then one of the following holds:
n = 2 or T is a path.
n Ou 5, l = 3, and T O YtO for some integer t Ou 2 with t O 1 .
3 O n O 4, l = 4, and T O J for some graph J OO J .
3 O n O 4, l Ou 5, and T O Zt for some integer t Ou 2.
, .
= .
, .
, .
, .
We think .
of Theorem 1.
1 is far from sufficient condition.
Therefore, we consider the converse of Theorem 1.
1 except for .
The result is the following.
Theorem 1.
Let l, n be integers with l Ou 3, n Ou 2, .
, .
= .
, .
, .
, .
, and let T be a connected graph of order at least 3.
Then GE4 ({Kl .
K1,n .
T }) is a finite family if and only if one of the following .
n = 2 or T is a path.
n Ou 5, l = 3, and T O YtO for some integer t Ou 2 with t O 1 .
3 O n O 4, l Ou 5, and T O Zt for some integer t Ou 2.
, .
= .
, .
, .
, .
We prove Theorem 1.
1 in Section 3.
We prove Theorem 1.
2 in Section 4.
Preliminary resullts The following result can be found in .
Lemma 2.
1 (Diestel .
Proposition 9.
Let l, n and t be integers with l Ou 3, n Ou 2 and t Ou 3.
Then GE1 ({Kl .
K1,n .
Pt }) is a finite family.
The following result can be found in .
Lemma 2.
2 (Buelban et al.
Theorems 10-.
Let l, n be integers with l Ou 3, n Ou 2, and let T be a connected graph of order at least 3.
If G4 ({Kl .
K1,n .
T }) is a finite family, then one of the following holds:
l Ou 4, n Ou 5.
T is a path.
l = 3, n Ou 5.
T OO T2 .
T OO T1O , l = 4, .
l Ou 4, 3 O n O 4, and T OO T2O , l Ou 5.
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Figure 4.
Graph B .
n = 2 or .
, .
= .
, .
, .
, .
In .
Case 1 in Lemma 5.
, a proposition which asserts that we have diam(G) O 7 for a 3connected {K3 .
Y3O }-free graph G was proved.
In the proof of the proposition, the 3-connectedness of G was used only to ensure that (G) Ou 3.
Thus we obtain the following lemma.
Lemma 2.
3 (Egawa et al.
Case 1 in Lemma 5.
Let G be a connected {K3 .
Y3O }-free graph with (G) Ou 4.
Then diam(G) O 7.
The following result can be found in .
Lemma 2.
4 (Egawa and Furuya .
Proposition 3.
Let t be an integer with t Ou 4 and t O 1 .
, and let t = 4, 2t 3, t Ou 6.
Let G be a connected {K3 .
YtO }-free graph with (G) Ou 4.
Then diam(G) O d.
Proof of Theorem 1.
Let B be the graph depicted in Figure 4.
For an integer s Ou 2, let Hs be the obtained from s .
pairwise vertex-disjoint copies B1 .
B2 , .
Bs of B such that V (Bi ) = .
j , vj,h | 1 O j O 2, 1 O .
h O .
where uj and vj,h respectively correspond to uj and vj,h , by adding edges u2 u1 indices i and i 1 are read modulo s.
Lemma 3.
Let s be an integer with s Ou 2, and let T be a graph such that T O Hs .
If T OO T2 , then T O YtO for some integer t Ou 2 with t O 1 .
Proof.
First assume that T OE Pl .
Ou .
If l Oe 2 O 1 .
, then letting t = l Oe 2, we get t O 1 .
and T OE Pt 2 O YtO .
if l Oe 2 O 1 .
, then letting t = l Oe 1, we get t O 1 .
and T OE Pt 1 O Pt 2 O YtO .
Next assume that T OE Ym .
Ou .
If m Oe 1 O 1 .
, then letting t = m Oe 1, we get t O 1 .
and T OE Yt 1 O YtO .
if m Oe 1 O 1 .
, then letting t = m, we get t O 1 .
and T OE Yt O Yt 1 O YtO .
Therefore, we may assume T OE YnOA for nA Ou 2.
Then OI(T ) = 3.
Now, we divide the proof into the following two cases:
Stars in forbidden triples generating a finite set of graphs .
Takafumi Kotani .
Case 1.
uj OO V (T ) and dT .
j ) = 3 for some 1 O i O s and 1 O j O 2.
Without loss of generality, we may assume u2 OO V (T ) and dT .
2 ) = 3.
First, we assume .
2,1 , v2,2 , v2,3 } OI V (T ).
Since T has no cycle, v1,p OO V (T ) for any 1 O p O 3.
Then T OE K1,3 , .
which contradicts T OE YnOA .
Hence, we may assume .
2,1 , v2,2 , u1 } OI V (T ).
Since T has no .
cycle, we have v1,p OO V (T ) for any 1 O p O 3.
Let i1 be the maximum integer such that 1 O i1 O s .
) .
and u1 1 OO V (T ).
Since T has no cycle, |V (T ) O .
j,1 , vj,2 , vj,3 }| = 1 for any 1 O i O i1 Oe 1 .
and 1 O j O 2.
Therefore, we may assume .
j,1 | 1 O i O i1 Oe 1, 1 O j O .
OI V (T ).
) .
) .
) u1 OO V (T ), then T OE Y4sOe2 .
Thus we may assume i1 = s.
If V (T ) O .
2,11 , v2,21 , v2,31 } = OI, then .
) .
) .
) .
) V (T ) OI .
j , vj,1 | 1 O i O i1 Oe 1, 1 O j O .
O .
2 , v2,1 , v2,2 , u1 1 , v1,11 , v1,21 , v1,31 }, which .
) .
) .
) .
) implies that T O Y4iO1 Oe2 .
Thus we may assume V (T ) O .
2,11 , v2,21 , v2,31 } = OI, say v2,11 OO V (T ).
) .
) .
) .
) Since T has no cycle, we have |V (T ) O .
1,11 , v1,21 , v1,31 }| = 1, say v1,11 OO V (T ).
Since T has no .
) .
) .
) cycle and OI(T ) = 3, we have |V (T ) O .
2,21 , v2,31 , u2 1 }| O 1.
Then .
) .
) .
) .
) .
) .
) .
) .
) .
V (T ) OI .
j , vj,1 | 1 O i O i1 Oe 1, 1 O j O .
O .
2 , v2,1 , v2,2 , u1 1 , v1,11 , v2,11 , v2,21 }.
V (T ) OI .
j , vj,1 | 1 O i O i1 Oe 1, 1 O j O .
O .
2 , v2,1 , v2,2 , u1 1 , v1,11 , v2,11 , v2,31 }, or .
V (T ) OI .
j , vj,1 | 1 O i O i1 , 1 O j O .
O .
2 , v2,1 , v2,2 }, which implies that T O Y4iO1 Oe1 or T O Y4i1 1 (O Y4iO1 ).
Consequently, we obtain the desired .
Case 1.
dT .
j ) O 2 for any 1 O i O s and 1 O j O 2 with uj OO V (T ).
We may assume v2,1 OO V (T ) and dT .
2,1 ) = 3.
First, we assume .
1,1 , v1,2 , v1,3 } OI V (T ).
Since .
T has no cycle, u1 , v2,2 , v2,3 OO V (T ).
Then T OE K1,3 , which contradicts the assumption that .
T OE YnOA .
Hence, we may assume .
1,1 , v1,2 , u2 } OI V (T ).
Since T has no cycle, we have .
) u1 , v2,2 , v2,3 OO V (T ).
Let i2 be the minimum integer such that 1 O i2 O s and u1 2 OO V (T ).
If i2 = 1, then T OE K1,3 , which contradicts the assumption that T OE YnA .
Thus we may assume .
that i2 Ou 2.
Since T has no cycle, |V (T ) O .
j,1 , vj,2 , vj,3 }| = 1 for any 1 O i O i2 Oe 2 and .
1 O j O 2.
Therefore, we may assume .
j,1 | 1 O i O i2 Oe 2, 1 O j O .
OI V (T ).
Oe.
Oe.
Oe.
V (T ) O .
1,12 , v1,22 , v1,32 } = OI.
V (T ) = .
j , vj,1 | 1 O i O i2 Oe 2, 1 O j O .
O .
Oe.
1,1 , v1,2 , v2,1 , u2 , u1 2 }, which implies that T OE Y4i2 Oe5 (O Y4iO2 Oe6 ).
Thus we assume V (T ) O .
Oe.
Oe.
Oe.
Oe.
Oe.
Oe.
Oe.
1,12 , v1,22 , v1,32 } = OI.
Since dT .
1 2 ) O 2, |V (T ) O .
1,12 , v1,22 , v1,32 }| = 1, say .
Oe.
Oe.
Oe.
Oe.
v1,12 OO V (T ).
If V (T ) O .
2,12 , v2,22 , v2,32 } = OI.
V (T ) = .
j , vj,1 | 1 O i O i2 Oe 2, 1 O .
Oe.
Oe.
j O .
O .
1,1 , v1,2 , v2,1 , u2 , u1 2 , v1,12 }, which implies that T OE Y4i2 Oe4 (O Y4iO2 Oe5 ).
Thus we .
Oe.
Oe.
Oe.
Oe.
may assume V (T ) O .
2,12 , v2,22 , v2,32 } = OI, say v2,12 OO V (T ).
Since T has no cycle and Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Figure 5.
Graph C .
Oe.
OI(T ) = 3, we have |V (T ) O .
2,22 .
Oe.
, v2,32 .
Oe.
, u2 2 }| O 1.
Then .
Oe.
, v1,12 .
Oe.
, v1,12 .
V (T ) OI .
j , vj,1 | 1 O i O i2 Oe 2, 1 O j O .
O .
1,1 , v1,2 , v2,1 , u2 , u1 2 V (T ) OI .
j , vj,1 | 1 O i O i2 Oe 2, 1 O j O .
O .
1,1 , v1,2 , v2,1 , u2 , u1 2 .
Oe.
, v2,12 .
Oe.
, v2,22 .
Oe.
, v2,12 .
Oe.
Oe.
, v2,32 .
Oe.
V (T ) OI .
j , vj,1 | 1 O i O i2 Oe 1, 1 O j O .
O .
1,1 , v1,2 , v2,1 , u2 }, which implies that T O Y4iO 2 Oe4 or T O Y4i2 Oe2 (O Y4iO 2 Oe3 ).
Consequently, we obtain the desired conclusion.
Let C be the graph depicted in Figure 5.
For an integer s Ou 2, let Hs be the graph obtained .
from s pairwise vertex-disjoint copies C1 .
C2 , .
Cs of C such that V (Ci ) = .
, w.
, vj,h | 1 O .
j O 2, 1 O h O .
where u.
, w.
and vj,h respectively correspond to u, w and vj,h , by adding .
edges v2,1 u.
, v2,2 u.
where indices i and i 1 are read modulo s.
Lemma 3.
Let s be an integer with s Ou 2, and let T be a graph such that T O Hs .
If T OO T0O and 3.
Oe .
> |V (T )|, then T O J for some graph J OO J .
Proof.
Since T OO T0O .
ote that |V (T )| Ou .
, there exists the integer i with 1 O i O s such that u.
OO V (T ).
Hence, since 3.
Oe .
> |V (T )|, there exists the integer i3 with 1 O i3 O s such that u.
3 ) OO V (T ) and u.
OO V (T ).
Without loss of generality, we may assume i3 = s.
Let i4 be the maximum integer such that 1 O i4 O s Oe 1 and u.
4 ) OO V[ (T ).
For each 1 O i O i4 and i = s, let .
T .
:= T O G[V (Ci ) O .
i 1 }].
Note that T = T O ( T .
1OiOi4 Claim 1.
One of the following holds:
T .
OE K1 .
T .
O A4 and u.
is the last vertex of A4 .
T .
O A2 and u.
is the last vertex of A2 .
T .
O A3 and u.
is the last vertex of A3 .
Stars in forbidden triples generating a finite set of graphs .
Takafumi Kotani .
Proof.
If |V (T .
) O .
2,1 , v2,2 }| = 0, then V (T .
) = .
}, and hence .
Thus, we may .
assume 1 O |V (T .
) O .
2,1 , v2,2 }| O 2.
Case 1.
|V (T .
) O .
2,1 , v2,2 }| = 1.
Without loss of generality, we may assume v2,1 OO V (T .
In the case where |V (T .
) O .
1,1 , w.
}| = 0, we have V (T .
) = .
2,1 , u.
},which implies that T .
O A4 .
Thus .
In the case where |V (T .
) O .
1,1 , w.
}| = 1, without loss of generality, we may assume .
v1,1 OO V (T .
Then V (T .
) = .
1,1 , v2,1 , u.
} or V (T .
) = .
1,1 , v1,2 , v2,1 , u.
},which implies that T .
O A4 .
Thus .
In the case where |V (T .
) O .
1,1 , w.
}| = 2, we have v1,2 OO V (T .
) since T OO T0O .
Hence .
V (T .
) = .
1,1 , w.
, v2,1 , u.
}, which implies that T .
O A2 .
Thus .
Case 2.
|V (T .
) O .
2,1 , v2,2 }| = 2.
In this case, we have w.
OO V (T .
) and |V (T .
) O .
1,1 , v1,2 }| O 1 since T OO T0O .
In the .
case where |V (T .
) O .
1,1 , v1,2 }| = 0, we have V (T .
) = .
2,1 , v2,2 , u.
},which implies that .
T .
O A3 .
If |V (T .
) O .
1,1 , v1,2 }| = 1, we may assume v1,1 OO V (T .
Then V (T .
) = .
1,1 , v2,1 , v2,2 , u.
},which implies that T .
O A3 .
Consequently, .
Claim 2.
One of the following holds:
T .
4 ) OE K1 .
T .
4 ) O A4 and u.
4 ) is the first vertex of A4 .
T .
4 ) O A2 and u.
4 ) is the first vertex of A2 .
T .
4 ) O A1 and u.
4 ) is the first vertex of A1 .
) .
) Proof.
If |V (T .
4 ) ) O .
1,14 , v1,24 }| = 0, then V (T .
4 ) ) = .
4 ) }, and hence .
Thus, we .
) .
) may assume that 1 O |V (T .
4 ) ) O .
1,14 , v1,24 }| O 2.
) .
) Case 1.
|V (T .
4 ) ) O .
1,14 , v1,24 }| = 1.
) Without loss of generality, we may assume v1,14 OO V (T .
4 ) ).
) .
) In the case where |V (T .
4 ) ) O .
2,14 , w.
4 ) }| = 0, we have V (T .
4 ) ) = .
4 ) , v1,14 }, which implies T .
4 ) O A4 .
Thus, .
) In the case where |V (T .
4 ) ) O .
2,14 , w.
4 ) }| = 1, without loss of generality, we may assume .
) .
) .
) .
) .
) .
) v2,14 OO V (T .
4 ) ).
Then V (T .
4 ) ) = .
4 ) , v1,14 , v2,14 } or V (T .
4 ) ) = .
4 ) , v1,14 , v2,14 , v2,24 }, which implies T .
4 ) O A4 .
Thus, .
) .
In the case where |V (T .
4 ) ) O .
2,14 , w.
4 ) }| = 2.
Then we have v2,2 OO V (T .
4 ) ) since T OO T0O .
) .
) Thus V (T .
4 ) ) = .
4 ) , v1,14 , v2,14 , w.
4 ) }, which implies T .
4 ) O A2 .
Thus .
) .
) Case 2.
|V (T .
4 ) ) O .
1,14 , v1,24 }| = 2.
Stars in forbidden triples generating a finite set of graphs .
) .
) Takafumi Kotani In this case, we have w.
4 ) OO V (T .
4 ) ) and |V (T .
4 ) ) O .
2,14 , v2,24 }| O 1 since T OO T0O .
In the .
) .
) .
) .
) case where |V (T .
4 ) ) O .
2,14 , v2,24 }| = 0, we have V (T .
4 ) ) = .
4 ) , v1,14 , v2,14 }, which implies T .
4 ) O A1 .
Thus, .
) .
) .
) In the case where |V (T .
4 ) ) O .
2,14 , v2,24 }| = 1, we may assume v2,14 OO V (T .
4 ) ).
Then .
) .
) V (T .
4 ) ) = .
4 ) , v1,14 , v2,14 }, which implies T .
4 ) O A1 .
Consequently, .
Claim 3.
For each i with 1 O i O i4 Oe 1, one of the following holds:
T .
OE A4 , u.
is the first vertex of A4 and u.
is the last vertex of A4 .
T .
O A3 , u.
is the first vertex of A3 and u.
is the last vertex of A3 .
T .
OE A2 , u.
is the first vertex of A2 and u.
is the last vertex of A2 .
T .
OE A1 , u.
is the first vertex of A1 and u.
is the last vertex of A1 .
Proof.
Since T is connected, we have u.
, u.
OO V (T .
) and 1 O |V (T .
) O .
1,1 , v1,2 }| O 2.
Case 1.
|V (T .
) O .
1,1 , v1,2 }| = 1.
We may assume that v1,1 OO T .
Since T .
is connected, we have 1 O |V (T .
) O .
, v2,1 }| O 2.
Suppose that |V (T .
) O .
, v2,1 }| = 1.
In the case where w.
OO T .
, we have V (T .
) = .
, v1,1 , w.
, v2,2 , u.
}, which implies T .
OE A4 .
Thus, .
In the case where v2,1 OO .
T .
, we have V (T .
) = .
, v1,1 , v2,1 , u.
} or V (T .
) = .
, v1,1 , v2,1 , v2,2 , u.
}, which implies T .
is a path with order 4 or T .
OE A3 .
Thus .
Suppose that |V (T .
) O .
, v2,1 }| = 2.
Since T .
OO T0O , we have v2,2 OO T .
Hence we .
have V (T .
) = .
, v1,1 , w.
, v2,1 , u.
}, which implies T .
OE A2 .
Thus, .
Case 2.
|V (T .
) O .
1,1 , v1,2 }| = 2.
Since T .
is connected and T .
OO T0O , we have w.
OO T .
and |V (T .
)O.
2,1 , v2,2 }| = 1.
We may .
assume v2,1 OO V (T .
Then V (T .
) = .
, v1,1 , v1,2 , v2,1 , u.
}, which implies T .
OE A1 .
Consequently, .
T .
)) O J for some graph By the definition of J and Claims 1-3, we obtain T (= T .
O ( 1OiOi4 J OO J .
Consequently, the proof of Lemma 3.
2 is complete.
For an integer s Ou 2, let Hs be the graph obtained from s pairwise vertex-disjoint copies .
D1 .
D2 , .
Ds of K4 such that V (Di ) = .
, vj | 1 O j O .
by adding edges u.
v1 , .
v2 , u.
v3 where indices i and i 1 are read modulo s.
Lemma 3.
Let s be an integer with s Ou 2, and let T be a graph such that T O Hs .
If T OO T2O , then T O Zt for some integer t Ou 2.
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani .
Figure 6.
Graph Hs Proof.
If T is a path, then T O Zt , where t is the minimum integer such that t Ou |V (T )| Oe 1, as If T OE Zm for some integer m with m Ou 2, the assertion clearly holds.
Thus we may assume T OE ZnOA for nA Ou 2.
Then T contains a triangle.
Without loss of generality, we may assume .
1 , v2 , u.
} OI V (T ).
Note that u.
, v3 OO V (T ).
Let i5 be the maximum integer such that 1 O .
i5 O s Oe 1 and u.
5 ) OO V (T ).
Since T OE ZnO for some n Ou 2, we have |V (T ) O .
1 , v2 , v3 }| = 1 .
for any 2 O i O i5 .
Therefore we may assume .
1 | 2 O i O i5 } OI V (T ).
Since T OE ZnO .
for some n Ou 2, we have |V (T ) O .
1 5 , v2 5 , v3 5 }| = 2, say .
1 5 , v2 5 } OI V (T ).
Therefore we have V (T ) = .
, v1 | 2 O i O i5 } O .
, v1 , v2 , v1 5 , v2 5 }.
Hence O , which contradicts T OO T2O .
Consequently, we obtain the desired conclusion.
T OE Z2i 5 Oe1 Proof of Theorem 1.
Let l, n and T be as in Theorem 1.
1, and suppose that GE4 {Kl .
K1,n .
T } is a finite family.
Since G4 ({Kl .
K1,n .
T }) OI GE4 ({Kl .
K1,n .
T }).
G4 ({Kl .
K1,n .
T }) is also a finite It follows from Lemma 2.
2 that one of .
Oe .
in Lemma 2.
2 holds.
If either .
in Lemma 2.
2 holds, then one of .
Thus we may assume that either .
in Lemma 2.
2 holds.
Case 1.
in Lemma 2.
2 holds.
By .
in Lemma 2.
T OO T2 .
For each s Ou 2.
Hs is a connected {K3 .
K1,5 }-free graph with .
(Hs ) = 4.
Since GE4 ({Kl .
K1,n .
T }) is finite, there exists s1 Ou 2 such that T O Hs1 .
Then by Lemma 3.
T O YtO for some integer t Ou 2 with t O 1 .
Consequently .
Case 2.
in Lemma 2.
2 holds.
By .
in Lemma 2.
T OO T1O or T OO T2O .
Subcase 2.
T OO T1O .
Hs is a connected {K4 .
K1,3 }-free Note that T OO T0O since T1O OI T0O .
For each s > |V (T .
graph with (Hs ) = 4.
Since GE4 ({Kl .
K1,n .
T }) is finite, there exists s2 > |V (T 1 such that .
T O Hs2 .
Then by Lemma 3.
T O J for some graph J OO J .
Consequently .
Subcase 2.
T OO T2O .
For each s Ou 2.
Hs is a connected {K5 .
K1,3 }-free graph with (Hs ) Ou 4.
Since GE4 ({Kl .
K1,n , .
T }) is finite, there exists s3 Ou 2 such that T O Hs3 .
Then by Lemma 3.
T O Zt for some integer t Ou 2.
Consequently .
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Proof of Theorem 1.
By Theorem 1.
1, the Ayonly ifAy part of Theorem 1.
2 holds.
In this section, we prove the AyifAy part of Theorem 1.
It is suffices to show that (A.
GE4 ({Kl .
K1,2 .
T }) .
Ou 3.
T is a connected grap.
are finite families.
(A.
GE4 ({Kl .
K1,n .
Pt }) .
Ou 3, n Ou 2, t Ou .
are finite families.
(A.
GE4 ({K3 .
K1,n .
YtO }) .
Ou 5, t Ou 2 with t O 1 .
) are finite families.
(A.
GE4 ({Kl .
K1,n .
Zt }) .
Ou 5, 3 O n O 4, t Ou .
are finite families.
(A.
GE4 ({K3 .
K1,n .
T }) .
O n O 4.
T is a connected grap.
are finite families.
Since GE4 ({Kl .
K1,2 .
T }) OI GE1 ({Kl .
K1,2 }) = GE1 ({Kl .
K1,2 .
P3 }) and GE4 ({Kl .
K1,n .
Pt }) OI GE1 ({Kl .
K1,n .
Pt }), it follows from Lemma 2.
1 that (A.
and (A.
Let G be a connected K3 -free graph with (G) Ou 4, and let w OO V (G).
Then NG .
is an independent set of G and there are 4 vertices x1 , x2 , x3 , x4 OO NG .
, and G[.
, x1 , x2 , x3 , x4 }] OE K1,4 .
In particular, for any integer n with 3 O n O 4.
GE4 ({K3 .
K1,n }) = OI, which proves (A.
Thus, in the remainder of this section, we show that (A.
and (A.
Let l and n be integers with l Ou 3 and n Ou 3, and let G be a graph having a vertex w of degree at least R.
Oe 1, .
Then by the definition of R.
Oe 1, .
NG .
contains a clique C of order l Oe 1 or an independent set I of size n.
If the former holds, then .
O C induces a copy of Kl in if the latter holds, then .
O I induces a copy of K1,n in G.
This implies that the maximum degree of a {Kl .
K1,n }-free graph is bounded by a constant R.
Oe 1, .
Oe 1 .
hich depends on l and .
Furthermore, it follows from Lemmas 2.
3 and 2.
4 that for each t Ou 3 with t O 1 .
, the diameter of a connected {K3 .
YtO }-free graph is bounded by the constant which depends on Since it is known that every connected graph G satisfies |V (G)| O OI(G)diam(G) 1 .
ee, for example,.
), the following propositions will complete the proof of (A.
and (A.
A The diameter of all connected {K3 .
Y2O }-free graphs G with (G) Ou 4 is bounded by a constant (Proposition 4.
A For a fixed integer t with t Ou 2, the diameter of all connected {K1,4 .
Zt }-free graphs G with (G) Ou 4 is bounded by a constant (Proposition 4.
We start with the following fundamental lemmas.
Lemma 4.
Let G be a connected graph.
Let u and v be two vertices of G, and let Q = u0 u1 .
be a shortest u-v path of G, where l = distG .
, .
, u0 = u and ul = v.
Let t, tA be integers with 0 O tA < t O l.
Then the following hold.
If t Oe tA Ou 2, then ut utA OO E(G).
If t Oe tA Ou 3, then NG .
t ) O NG .
tA ) Oe V (Q) = OI.
Proof.
This lemma immediately follows from the assumption that Q is a shortest u-v path.
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Lemma 4.
Let G be a connected K3 -free graph.
Let u and v be two vertices of G, and let Q = u0 u1 .
ul be a u-v path of G, where u0 = u and ul = v.
Then the following hold.
For any integers t and tA with 0 O tA < t O l, if tOetA = 1, then NG .
t )ONG .
tA )OeV (Q) = OI.
For any integer t with 1 O t O l Oe 1.
E(NG .
t ) Oe V (Q), .
tOe1 , ut 1 }) = OI.
Proof.
Statement .
immediately follows from the assumption that G is K3 -free.
Statement .
immediately holds by .
The following lemma is used in the proof of Proposition 4.
Lemma 4.
Let l be an integer with l Ou 7, let G be a connected {K3 .
Y2O }-free graph with (G) Ou 4 and diam(G) Ou l.
Let u and v be two vertices of G such that l = distG .
, .
, and let Q = u0 u1 .
ul be a shortest u-v path of G, where u0 = u and ul = v.
Then for any i with 0 O i O l Oe 7.
NG .
j ) O NG .
j 2 ) Oe V (Q) = OI for some j with i O j O i 5.
Proof.
Let i be an integer with 0 O i O l Oe 7.
By way of contradiction, suppose that NG .
j ) O NG .
j 2 ) Oe V (Q) = OI .
for any j with i O j O i 5.
Since (G) Ou 4, |NG .
t ) Oe V (Q)| Ou 2.
For each t with 0 O t O l, we take two vertices at , bt OO NG .
t ) Oe V (Q).
Since G is K3 -free, at bt OO E(G) .
for 0 O t O l.
For t, tA with i O t < tA O i 7, .
t , bt } O .
tA , btA } = OI .
by Lemma 4.
Lemma 4.
Let k be an integer with i 1 O k O i 5.
Take two vertices x OO .
k , bk } and y OO .
k 1 , bk 1 } .
ote that x = y by .
Since G is Y2O -free.
kOe1 , uk , uk 1 , uk 2 , x, .
OE Y2O , which implies for any vertices x OO .
k , bk } and y OO .
k 1 , bk 1 }, xy OO E(G) by Lemma 4.
Lemma 4.
Since k is arbitrary, for any vertices x OO .
t , bt } and y OO .
t 1 , bt 1 }, xy OO E(G) .
for any t with i 1 O t O i 5.
Since G is K3 -free, there is no edge between .
t , bt } and .
t 2 , bt 2 } .
for any t with i 1 O t O i 4.
Since G is Y2O -free.
i 2 , ai 3 , ai 4 , ai 5 , bi 2 , bi 5 ] OE Y2O , which implies that there exists an edge between .
i 2 , bi 2 } and .
i 5 , bi 5 } by .
, .
Without loss of generality, we may assume that ai 2 ai 5 OO E(G) .
ee Figure .
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Figure 7.
i 2 , ai 3 , ai 4 , ai 5 , bi 2 , bi 5 ] Figure 8.
i 2 , ai 5 , ai 1 , bi 1 , ai 6 , bi 6 ] Since G is K3 -free, ai 1 ai 5 , bi 1 ai 5 , ai 6 ai 2 , bi 6 ai 2 OO E(G).
Since G is Y2O -free.
i 2 , ai 5 , ai 1 , bi 1 , ai 6 , bi 6 ] OE Y2O , which implies that there exists an edge between .
i 1 , bi 1 } and .
i 6 , bi 6 } by .
, .
Without loss of generality, we may assume that ai 1 ai 6 OO E(G) .
ee Figure .
Then u0 u1 .
ui 1 ai 1 ai 6 ui 6 .
ul is a shortest u-v path of G having length .
Oe .
} = l Oe 2, which contradicts the fact that distG .
, .
= l.
Proposition 4.
Let G be a connected {K3 .
Y2O }-free graph with (G) Ou 4.
Then diam(G) O 15.
Proof.
By way of contradiction, suppose that diam(G) Ou 16.
Take two vertices u and v of G with distG .
, .
= 16, and let Q = u0 u1 .
u16 be a shortest u-v path of G, where u0 = u and u16 = v.
By Lemma 4.
NG .
j1 ) O NG .
j1 2 ) Oe V (Q) = OI for some j1 with 0 O j1 O 5.
Let aj1 2 be a vertex of G with aj1 2 OO NG .
j1 ) O NG .
j1 2 ) Oe V (Q).
By Lemma 4.
NG .
i ) O NG .
i 2 ) Oe V (Q) = OI for some i with j1 3 O i O j1 8.
Let j2 be a minimum integer with j1 3 O j2 O j1 8 such that NG .
j2 ) O NG .
j2 2 ) Oe V (Q) = OI.
Hence, for any j A with j1 3 O j A O j2 Oe 1.
NG .
j A ) O NG .
j A 2 ) Oe V (Q) = OI.
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Figure 9.
u-v path of G Let aj2 be a vertex of G with aj2 OO NG .
j2 ) O NG .
j2 2 ) Oe V (Q).
Since (G) Ou 4.
NG .
t ) Oe V (Q) = OI for all t with j1 3 O t O j2 Oe 1.
For each t with j1 3 O t O j2 Oe 1, take a vertex at OO NG .
t ) Oe V (Q).
Since G is a Y2O -free.
m , um 1 , um 2 , um 3 , am 1 , am 2 ] OE Y2O for any m with j1 3 O m O j2 Oe 2.
Hence .
j1 4 aj1 5 , aj1 5 aj1 6 , .
, aj2 Oe1 aj2 } OI E(G) .
by Lemma 4.
Lemma 4.
, and .
If uj1 2 aj1 4 OO E(G), then u0 u1 .
uj1 2 aj1 4 aj1 5 .
aj2 Oe1 aj2 uj2 2 uj2 3 .
u16 is a u-v path of G having length .
2 Oe .
} 1 .
Oe .
} = 14, which contradicts the fact that distG .
, .
= 16.
Thus we may assume that uj1 2 aj1 4 OO E(G).
Therefore, since G is a Y2O -free.
j1 2 , uj1 3 , uj1 4 , uj1 5 , aj1 3 , aj1 4 ] OE Y2O , we obtain aj1 3 aj1 4 OO E(G) .
by Lemma 4.
Lemma 4.
, and .
If uj1 1 aj1 3 OO E(G), then u0 u1 .
uj1 1 aj1 3 aj1 4 .
aj2 Oe1 aj2 uj2 2 uj2 3 .
u16 is a u-v path of G having length .
2 Oe .
} 1 .
Oe .
} = 14, which contradicts the fact that distG .
, .
= 16.
Thus, we may assume that uj1 1 aj1 3 OO E(G).
If aj1 2 uj1 4 OO E(G), then u0 u1 .
uj1 aj1 2 uj1 4 uj1 5 .
u15 u16 is a u-v path of G having length j1 1 1 .
Oe .
} = 14, which contradicts the fact that distG .
, .
= 16.
Thus, we may assume that aj1 2 uj1 4 OO E(G).
Therefore, since G is a Y2O -free.
j1 1 , uj1 2 , uj1 3 , uj1 4 , aj1 2 , aj1 3 ] OE Y2O , and hence we aj1 2 aj1 3 OO E(G) .
by Lemma 4.
Lemma 4.
, and .
Consequently, we obtain u0 u1 .
uj1 aj1 2 aj1 3 .
aj2 Oe1 aj2 uj2 2 uj2 3 .
u16 by .
, .
is a u-v path of G having length j1 1 .
2 Oe .
} 1 .
Oe .
} = 14, which contradicts the fact that distG .
, .
= 16 .
ee Figure .
Proposition 4.
Let t be an integer with t Ou 2, and let G be a connected {K1,4 .
Zt }-free graph with (G) Ou 4.
Then diam(G) O 2t Oe 1.
Stars in forbidden triples generating a finite set of graphs Takafumi Kotani Proof.
Suppose that diam(G) Ou 2t.
Take two vertices u and v of G with distG .
, .
= 2t, and let u0 u1 .
u2t be a shortest u-v path of G, where u0 = u and u2t = v.
By (G) Ou 4, we can take two distinct vertices at , aAt OO NG .
t ) Oe .
tOe1 , ut 1 }.
Since G is K1,4 -free.
t , utOe1 , ut 1 , at , atA ] OE K1,4 , i.
tOe1 , ut 1 , at , atA } is not an independent set of G.
With Lemma 4.
in mind, we divide the proof into two cases.
Case 1.
E(.
tOe1 , ut 1 }, .
t , atA }) = OI.
Without loss of generality, we may assume that utOe1 at OO E(G).
Since G is Zt -free, neither .
t , at , utOe1 , .
, u0 } nor .
tOe1 , at , ut , .
, u2tOe1 } induces a copy of Zt in G.
Thus, there exist indices i1 and i2 with 0 O i1 O t Oe 2 and t 1 O i2 O 2t Oe 1 such that ui1 at , ui2 at OO E(G) by Lemma 4.
Then u0 u1 .
ui1 at ui2 ui2 1 .
u2t is a u-v path of G having length i1 2 .
t Oe i2 ) (O .
Oe .
2 2t Oe .
= 2t Oe .
, which contradicts the fact that distG .
, .
= 2t.
Case 2.
at aAt OO E(G) Since G is Zt -free, neither .
t , aAt , ut , .
, u1 } nor .
t , aAt , ut , .
, u2tOe1 } induces a copy of Zt in G.
Thus.
E(.
1 , u2 , .
, utOe2 }, .
t , atA }) = OI and E(.
t 2 , ut 3 , .
, u2tOe1 }, .
t , atA }) = OI by Lemma 4.
Let b OO .
t , aAt } and uj1 OO .
1 , u2 , .
, utOe2 } be two vertices such that buj1 OO E(G), and let bA OO .
t , aAt } and uj2 OO .
t 2 , ut 3 , .
, u2tOe1 } be two vertices such that bA uj2 OO E(G).
Note that if b = bA then bbA OO E(G).
If b = bA , then u0 u1 .
uj1 buj2 uj2 1 .
u2t is a u-v path of G having length j1 2 .
t Oe j2 ) (O .
Oe .
2 2t Oe .
= 2t Oe .
, which contradicts the fact that distG .
, .
= 2t.
b = bA , then u0 u1 .
uj1 bbA uj2 uj2 1 .
u2t is a u-v path of G having length j1 3 .
t Oe j2 ) (O .
Oe .
3 2t Oe .
= 2t Oe .
, which contradicts the fact that distG .
, .
= 2t.
Acknowledgement The authors are grateful to Professor Yoshimi Egawa and Professor Keiko Kotani for the helpful References