# Nonplanarity of Iterated Line Graphs

Authors: Jing Wang
Journal: Journal of Mathematics
 (2020)

---

## Abstract

The 1-crossing index of a graphG is the smallest integer k such that the kth iterated line graph of G has crossing number greater than 1. In this paper, we show that the 1-crossing index of a graph is either infinite or it is at most 5. Moreover, we give a full characterization of all graphs with respect to their 1-crossing index.


---

## Body

## 1. Introduction

We only consider simple, connected, and undirected graphG=VG,EG in this paper. For any vertex v in G, we denote the degree of v by dGv. A graph G is r-regular if dGv=r for all v∈VG. Denote by ΔG the maximum degree of vertices of G, i.e., ΔG=maxdGv|v∈VG. A cut-vertex (resp. cut-edge) of a connected graph G is a vertex (resp. edge) whose deletion results in a disconnected graph. A block of a graph G is a maximal connected subgraph of G that has no cut-vertex. For notations not defined here, the readers are referred to [1].A graph is planar if it can be drawn in the plane in such a way that no two of its edges intersect. The crossing number of a graphG, denoted by crG, is the smallest number of intersections of pairs of edges in any drawing of G in the plane. Obviously, G is planar if and only if crG=0. The crossing number of a graph was introduced by Turán [2], and crossing numbers of certain families of graphs were studied, see [3–8] and the references therein.The line graph ofG, denoted by LG, is defined as the graph whose vertices are the edges of G, i.e., VLG=EG, and two vertices in LG are adjacent if and only if the corresponding edges in G are incident to a common vertex.Given a graphG, we denote the kth iterated line graph of G by LkG, where LkG=LLk−1G. In particular, L0G=G is the original graph and L1G=LG is the line graph of G. Since iterated line graphs are well-suited for designing of interconnection networks, the investigation of iterated line graphs has recorded a large progress in recent years, see [9–12].In paper [13], Sedláček obtained the following result which characterized graphs whose line graph is planar.Lemma 1 (see [13]).
The line graph of a graphG is planar if and only if G is planar, ΔG≤4, and every vertex of degree 4 in G is a cut-vertex.Based on the above result, Ghebleh and Khatirinejad [14] began to study the planarity of iterated line graphs. They defined the line index of a graph G, denoted by ξG, to be the smallest k such that LkG is nonplanar. If LkG is planar for all k≥0, then ξG=∞.Corollary 1 in [15] showed that crG≤crLG. It is noted that a graph has line index 0 if and only if it is nonplanar. For a planar graph G, we have(1)ξG=1+maxk|LkGis planar.LetK1,3 be the complete bipartite graph with partite sets a and b1,b2,b3. Let t1,t2, and t3 be positive integers; we define Yt1,t2,t3 to be the graph obtained from K1,3 by subdividing the edge abi to a path of length ti (i∈1,2,3). We define Tt3 to be the graph obtained by adding two vertices b4 and b5 to Y1,1,t3 and joining them to b3, see Figure 1.Figure 1
The graphsYt1,t2,t3 and Tt3.
(a)(b)Ghebleh and Khatirinejad [14] showed that the line index of a graph is either infinite or it is at most 4. Moreover, with the graphs Hi1≤i≤4 depicted in Figure 2, a full characterization of all graphs with respect to their line index was given.Figure 2
The graphsHi1≤i≤4.
(a)(b)(c)(d)Lemma 2 (see [14]).
LetG be a connected graph. Then,(1)
ξG=0 if and only if G is nonplanar(2)
ξG=∞ if and only if G is either a path, a cycle, or K1,3(3)
ξG=1 if and only if G is planar and either ΔG≥5 or G has a vertex of degree 4 which is not a cut-vertex(4)
ξG=2 if and only if LG is planar and G contains one of the graphs Hi in Figure 2 as a subgraph(5)
ξG=4 if and only if G is one of the graphs Tt or Y1,1,t for some t≥2(6)
ξG=3, otherwiseIn 1971, Chartrand et al. [16] obtained a necessary and sufficient condition for graphs whose line graph is outerplanar.Lemma 3 (see [16]).
The line graphLG of a graph G is outerplanar if and only if ΔG≤3, and if dGv=3 for a vertex v of G, then v is a cut-vertex.Using this result, Lin et al. [17] investigated the outerplanarity of line graphs and iterated line graphs; they defined the outerplanar index of a graph G to be the smallest k such that LkG is nonouterplanar. They also showed that the outerplanar index of a graph is either infinite or it is at most 3; furthermore, they completely characterized all graphs with respect to their outerplanar index.Motivated by these results, we began to consider the problem of nonplanarity of iterated line graphs. Another motivation for this work is a result of Kulli et al. [18] and a result of Jendrol’ and Klešč [15], which characterized graphs whose line graphs have crossing number one.Lemma 4 (see [15, 18]).
The line graph of a planar graphG has crossing number one if and only if 1 or 2 holds:(1)
ΔG=4 and there is a unique noncut-vertex of degree 4(2)
ΔG=5, every vertex of degree 4 is a cut-vertex, there is a unique vertex of degree 5, and it has at most 3 incident edges in any blockLemma 5 (see [15]).
LetG be a nonplanar graph. Then, crLG=1 if and only if the following conditions hold:(1)
crG=1(2)
ΔG≤4, and every vertex of degree 4 is a cut-vertex of G(3)
There exists a drawing ofG in the plane with exactly one crossing in which each crossed edge is incident with a vertex of degree 2Here, we give similar results for the 1-crossing index of graphs.Definition 1.
The 1-crossing index of a graphG, denoted by ξ1G, is the smallest integer k such that crLkG>1. If crLkG≤1 for all k≥0, we define ξ1G=∞.It is inferred from Definition1 that ξ1G=0 if and only if crG>1. For a graph G whose crossing number is no more than one, we have(2)ξ1G=1+maxk|crLkG≤1.In this paper, we show that the 1-crossing index of a graph is either infinite or it is at most 5. Moreover, another purpose of this paper is to characterize all graphs with respect to their 1-crossing index.This paper is organized as follows. In Section2, we show that either ξ1G=∞ or ξ1G≤5 for any graph G; moreover, Theorems 1–3 characterize graphs with ξ1G=∞, ξ1G=0, or ξ1G=1, respectively. Our main efforts are dedicated to characterize graphs whose 1-crossing index is 2, 5, or 4 in Sections 3–5, respectively. Based on these results, graphs with 1-crossing index 3 can also be given since that is the only remaining case.


## 2. The Bound ofξ1G and Graphs with ξ1G = ∞ or ξ1G≤1

The following fact is clear; however, since it is used several times throughout this paper, we state it formally.Lemma 6.
IfH is a subgraph of G, then ξ1G≤ξ1H.Proof.
Letk=ξ1H. Then, crLkH>1 and crLkG≥crLkH>1 since H⊆G, which implies that ξ1G≤k.Lemma 7.
IfG is a graph with ΔG≥4, then ξ1G≤3.Proof.
IfΔG≥4, then G has K1,4 as a subgraph. It is easily seen that L2K1,4 is a 4-regular planar graph without cut-vertex, by Lemmas 1 and 4, crL3K1,4>1. By Lemma 6, ξ1G≤ξ1K1,4=3.LetPt and Ct denote, respectively, the path and cycle on t vertices and let P0 be the empty graph, namely, a graph with no vertices and no edges.Fort≥3, we define Xt to be the graph obtained by identifying a vertex of a cycle Ct with a vertex of P2.Lemma 8.
Fort≥3, we have ξ1Xt=4.Proof.
It is seen thatL2Xt is a planar graph with ΔL2Xt=4 and that L2Xt has a unique noncut-vertex of degree 4, thus crL3Xt=1 by Lemma 4. Furthermore, since ΔL3Xt=5, then we have crL4Xt>1 by Lemma 5. By Definition 1, ξ1Xt=4.Theorem 1.
For any graphG, we have ξ1G∈0,1,2,3,4,5,∞. Moreover, ξ1G=∞ if and only if G is a path, a cycle, or K1,3.Proof.
We knowLPt=Pt−1 for t≥1, LP0=P0, LCt=Ct, and LK1,3=C3. Therefore, ξ1G=∞ if G is a path, a cycle, or K1,3.
Next, assume thatG is distinct from a path, a cycle, and K1,3. First of all, we know that ΔG≥3.Case 1.ΔG≥4.Then, it hasξ1G≤3 according to Lemma 7Case 2.ΔG=3.Then,G either has Y1,1,2 or X3 as a subgraph since G is not K1,3. It can be verified that crL4Y1,1,2=1 and ΔL4Y1,1,2=5, thus crL5Y1,1,2>1 due to Lemma 5. Therefore, if G has Y1,1,2 as a subgraph, then ξ1G≤ξ1Y1,1,2=5; if G has X3 as a subgraph, then ξ1G≤ξ1X3=4 by Lemma 8.In [19], the authors present a structure characterization of graphs with crossing number one, the result lead to an equivalent description of graphs with crossing number at least 2.Lemma 9 (see [19]).
LetG be a nonplanar graph and let H be a Kuratowski subgraph of G. Then, crG≥2 if and only if, for every crossing pair e,f of H, e,f are separated by cycles in G or at least one of G−e and G−f is not planar.As a corollary of Lemma9, we can characterize graphs for which ξ1G=0.Theorem 2.
For any graphG, ξ1G=0 if and only if the following conditions hold:(1)
G is nonplanar(2)
LetH be a Kuratowski subgraph of G. For every crossing pair e,f of H, e,f are separated by cycles in G or at least one of G−e and G−f is not planarWe end this section by characterizing graphs for whichξ1G=1 in terms of Lemmas 4 and 5.Theorem 3.
For any graphG, ξ1G=1 if and only if one of the following conditions holds:(1)
G is a planar graph with ΔG=4, and there are at least two noncut-vertices of degree 4(2)
G is a planar graph with ΔG=5, and there are at least two vertices of degree 5(3)
G is a planar graph with ΔG=5; there is a unique vertex of degree 5 and there is at least one noncut-vertex of degree 4(4)
G is a planar graph with ΔG=5, every vertex of degree 4 is a cut-vertex, and there is a unique vertex of degree 5; however, it has at least 4 incident edges in one block(5)
G is a planar graph with ΔG≥6(6)
crG=1 and ΔG≥5(7)
crG=1, ΔG≤4, and there exists a noncut-vertex of degree 4(8)
crG=1, ΔG≤4, and every vertex of degree 4 is a cut-vertex; however, there does not exist a good drawing of G satisfying condition (3) in Lemma 5


## 3. Graphs withξ1G = 2

We useG¯ to denote the complement of a graph G. Let G and H be two vertex-disjoint graphs; G∨H denotes the join of graphs G and H. In the proof of Theorem 2 in [20], we found the following result to be useful.Proposition 1 (see [20]).
LetG has a vertex v of degree 4 that is not a cut-vertex. Then, G contains a subgraph either homeomorphic to P4∨K1 or to K2∨K3¯.To characterize graphs withξ1G=2, the graphs Hi1≤i≤4 depicted in Figure 2 are needed. Moreover, the graph H5 defined below is also meaningful in the following discussions.Definition 2.
DefineH5 to be the graph satisfying the following four conditions:(1)
crH5=1(2)
ΔH5≤4, and every vertex of degree 4 is a cut-vertex(3)
For any noncut-edgef=uv∈EH5, it has 4≤dH5u+dH5v≤5(4)
For any drawing ofLH5 with exactly one crossing, at least one of the crossed edge is not incident with vertices of degree 2Remark 1.
By conditions (1) and (2) of Definition2, G contains a subgraph homeomorphic to K3,3. The third condition of Definition 2 implies that there exists a drawing of H5 with exactly one crossing in which each crossed edge is incident with a vertex of degree 2. Thus, crLH5=1.Lemma 10.
LetG be a graph with crLG=1 and ξ1G=2. Then, G is either H5 or has a subgraph isomorphic to one of the graphs K1,5,H1,H2,H3, and H4.Proof.
LetG be a graph with crLG=1 and ξ1G=2. First of all, we have ΔG≤5. Since crL2G>1, by Lemma 5, either LG has a vertex of degree at least 5; or ΔLG=4 and there is a noncut-vertex of degree 4 in LG; or ΔLG≤4, and every vertex of degree 4 is a cut-vertex in LG; however, there does not exist a good drawing of LG in the plane satisfying condition (3) of Lemma 5.Case 1.LG has a vertex, say e, of degree at least 5.Recall thatΔG≤5, then G contains either K1,5, H1, H2, H3, or H4 as a subgraph.Case 2.ΔLG=4 and there is a noncut-vertex, say e, of degree 4 in LG.Case 2.1.e is a noncut-edge of G.Hence,G has a cycle containing e. Since e has degree 4 in LG, G contains either H2, H3, or H4 as a subgraph.Case 2.2. e is a cut-edge of G.Sincee is a noncut-vertex of LG, then e must be a pendant edge in G. By the condition that dLGe=4 and that ΔLG=4; thus, G must be K1,5.Case 3.ΔLG≤4, and every vertex of degree 4 in LG is a cut-vertex; however, there does not exist a good drawing of LG satisfying condition (3) of Lemma 5.Claim 1.ΔG≤4.Proof of Claim 1. Suppose to contrary that ΔG=5. Then, G=K1,5 since ΔLG≤4. Thus, LG has noncut-vertices of degree 4, a contradiction.Claim 2. Each vertex of degree 4 in G is a cut-vertex.Proof of Claim 2. Suppose to contrary that there is a noncut-vertex v of degree 4 in G. W.l.o.g., let ei1≤i≤4 be four edges incident with v in G. By Proposition 1, G contains a subgraph either homeomorphic to P4∨K1 or to K2∨K3¯, thus ei1≤i≤4 is not a bridge of G, which enforces that ei is a noncut-vertex of degree 4 in LG, a contradiction.Claim 3. For any noncut-edge f=uv∈EG, it has 4≤dGu+dGv≤5.Proof of Claim 3. Suppose to contrary that there is a noncut-edge f=uv with dGu+dGv≥6. Since ΔLG≤4, then dGu+dGv=6. Thus, f is a noncut-vertex of degree 4 in LG, a contradiction.SincecrLG=1, it follows from Claims 1 and 2 and Lemma 1 that crG=1. Moreover, by the assumption that ξ1G=2, G satisfies all of the conditions in Definition 1. Therefore, G is H5.Lemma 11.
LetG be a graph with crLG=0 and ξ1G=2. Then, G satisfies one of the following conditions:(1)
G has an edge that joins two vertices of degree 4(2)
G has at least two edges, each of whose degree sum of its two end vertices is 7(3)
There is only one edge inG such that the degree sum of its two end vertices is 7, and G has a subgraph isomorphic to H2, H3, or H4(4)
G has at least two noncut-edges whose degree sum of its two end vertices is 6Proof.
LetG be a graph with crLG=0 and ξ1G=2. Firstly, Lemma 1 tells that G is a planar graph with ΔG≤4. Secondly, crL2G>1 because ξ1G=2. By Lemma 4, the following three cases are discussed by considering the maximum degree of LG.Case 1.ΔLG≥6.We haveΔLG=6 since ΔG≤4. W.l.o.g., let f be a vertex of degree 6 in LG. Thus, each end vertex of f has degree 4 in G and G is the graph depicted in (1).Case 2.ΔLG=5.Case 2.1. There are at least two vertices of degree 5 in LG.W.l.o.g., letf1=u1v1 and f2=u2v2 be two vertices of degree 5 in LG. Therefore, dGui+dGvi=7, for i∈1,2 and G is the graph depicted in (2).Case 2.2. There is a unique vertex of degree 5 in LG, and LG has a noncut-vertex, say e, of degree 4.Then,G has a subgraph isomorphic to H2, H3, or H4. Thus, G is the graph depicted in (3).Case 2.3. Every vertex of degree 4 in LG is a cut-vertex; there is a unique vertex, say e, of degree 5 in LG; however, it has at least 4 incident edges in one block.W.l.o.g., assume thate=uv. Since dLGe=5 and ΔG≤4, we have that dGu,dGv=3,4. Because e has at least 4 incident edges in a block of LG, we conclude that e is not a bridge of G. Hence, G has a cycle containing e, which implies that G contains a subgraph isomorphic to H2, H3, or H4. Thus, G is the graph depicted in (3).Case 3.ΔLG=4.By Lemmas1 and 4, there are at least two noncut-vertices of degree 4 in LG since crL2G>1. W.l.o.g., let f1=u1v1 and f2=u2v2 be two noncut-vertices of degree 4 in LG. Therefore, for i∈1,2, dGui+dGvi=6 and fi is a noncut-edge in G. Thus, G is the graph depicted in (4).Theorem 4.
For any graphG, ξ1G=2 if and only if one of the conditions holds:(1)
crLG=1, and G has a subgraph either isomorphic to K1,5 or to Hi1≤i≤4(2)
G is H5(3)
LG is planar, and G has an edge that joins two vertices of degree 4(4)
LG is planar, and G has at least two edges, each of whose degree sum of its two end vertices is 7(5)
LG is planar, and there is only one edge in G such that the degree sum of its two end vertices is 7; moreover, G has a subgraph isomorphic to H2, H3, or H4(6)
LG is planar, and G has at least two noncut-edges whose degree sum of its two end vertices is 6Proof.
LetG be a graph with ξ1G=2. By the definition, we have crLG≤1 and crL2G>1. According to Lemmas 10 and 11, G is one of the graphs depicted in (1)–(6).
For the converse, we shall show thatξ1G=2 if G is one of the graphs depicted in (1)–(6).Case 1.G is the graph depicted in (1).LetH be K1,5 or one of the graphs Hi1≤i≤4. If H=K1,5, then LH either has a vertex of degree at least 5 or has a noncut-vertex of degree 4; if H=H1, then LH has a vertex of degree at least 5; finally, if H∈H2,H3,H4, then LH has a vertex of degree 4 which is a noncut-vertex. Lemma 5 yields that crL2H>1, thus crL2G≥crL2H>1. Since crLG=1, it follows that ξ1G=2.Case 2.G is the graph depicted in (2).By Remark1 and by the forth condition of Definition 2, we have crLG=1 and crL2G>1. Therefore, ξ1G=2.Case 3.G is the graph depicted in (3).W.l.o.g., letf be an edge of G that joins two vertices of degree 4, then dLGf=6. By Lemmas 1 and 4, crL2G>1. Since LG is planar, it follows that ξ1G=2.Case 4. G is the graph depicted in (4).W.l.o.g., letf1 and f2 be two edges whose degree sum of its two end vertices is 7 in G, then both f1 and f2 are vertices of degree 5 in LG. By Lemma 1, L2G is a nonplanar graph. Furthermore, we have crL2G>1 by Lemma 4. Therefore, ξ1G=2.Case 5.G is the graph depicted in (5).W.l.o.g., letf be the edge whose degree sum of its two end vertices is 7 in G, then dLGf=5. Moreover, G has a subgraph isomorphic to one of H2, H3, or H4. Note that there is a noncut-edge e in G, see Figure 2.Now, we consider the degree ofe in LG. If dLGe=4, then e is a noncut-vertex of degree 4 in LG and thus crL2G>1 by Lemma 4. If dLGe=5, that means e=f, then it can be verified that, in LG, e has at least 4 incident edges in one block, thus crL2G>1 by Lemma 4. Therefore, ξ1G=2.Case 6.G is the graph depicted in (6).W.l.o.g., letf1 and f2 be two noncut-edges whose degree sum of its two end vertices is 6 in G . Then, both f1 and f2 are noncut-vertices of degree 4 in LG. By Lemma 1, L2G is a nonplanar graph. Furthermore, by Lemma 4, we have crL2G>1 no matter ΔLG=4 or ΔLG=5. Therefore, ξ1G=2.


## 4. Graphs withξ1G = 5

Remind that the graphYt1,t2,t3 defined in Section 1 is obtained by subdividing each edge of K1,3 to a path of length ti (i∈1,2,3), respectively.Lemma 12.
Whent3≥3, we have ξ1Y1,1,t3=4. When t2≥2 and t3≥2, we have ξ1Y1,t2,t3=4.Proof.
Firstly, we prove thatξ1Y1,1,t3=4 when t3≥3. It is not difficult to see that L3Y1,1,t3 is a planar graph with ΔL3Y1,1,t3=4; moreover, there are at least two noncut-vertices of degree 4 in L3Y1,1,t3; therefore, crL4Y1,1,t3>1 according to Lemma 4. By Definition 1, ξ1Y1,1,t3=4 when t3≥3.
Now, we prove thatξ1Y1,t2,t3=4 when t2≥2 and t3≥2. One can see that L2Y1,t2,t3 is a planar graph with ΔL2Y1,t2,t3=4; moreover, L2Y1,t2,t3 has a unique noncut-vertex of degree 4; therefore, crL3Y1,t2,t3=1 by Lemma 4. Furthermore, ΔL3Y1,t2,t3=5, thus crL4Y1,t2,t3>1 by Lemma 5. By the definition, ξ1Y1,t2,t3=4.Theorem 5.
For any graphG, ξ1G=5 if and only if G=Y1,1,2.Proof.
Assuming thatG=Y1,1,2, it has been checked in Theorem 1 that crL4G=1 and that crL5G>1, thus ξ1G=5.
For the converse, letG be a graph with ξ1G=5. It follows from Lemma 2 and Theorem 1 that ΔG=3. Assuming that G is not a tree, by Lemmas 6 and 8, we have ξ1G≤ξ1Xt=4 since G contains Xt as a subgraph. This contradiction enforces that G is a tree. Moreover, Lemmas 6 and 12 indicate that G cannot have Y1,2,2 nor Y1,1,3 as a subgraph. All of the analyses assert that G=Y1,1,2.


## 5. Graphs withξ1G = 4

To characterize graphs withξ1G=4, the following graphs are introduced. Let J1 be the graph obtained by identifying a vertex of Ctt≥3 with a pendent vertex of P3. Define J2 to be the simple graph obtained from Ct by adding a path of arbitrary length to connect two vertices of Ct. Define J3 to be the graph obtained from Ct by adding two pendant edges, each to a vertex of Ct. These families of graphs are shown in Figure 3.Figure 3
The graphsJ1, J2, and J3.
(a)(b)(c)LetJ4 be a tree with diameter 3 such that two nonleaf vertices a1 and a2 both have degree 3. Denote J5 to be the graph obtained from J4 firstly by adding two new vertices v1 and v2 to J4 and joining vi to bii∈1,2 and then by subdividing the edge a1a2 to a path of length tt≥2. These families of graphs are depicted in Figure 4.Figure 4
The graphsJ4 and J5.
(a)(b)Lemma 13.
For1≤i≤5, we have ξ1Ji=3.Proof.
Wheni=1, it can be seen that L2J1 is a planar graph with at least two noncut-vertices of degree 4, then crL3J1>1 by Lemma 4. By the definition, ξ1J1=3.
Wheni=2, observe that, if the path added to Ct is of length greater than one, then L2J2 is a planar graph with at least two noncut-vertices of degree 4; if the path added to Ct is of length one, then crL2J2=1 and ΔL2J2=5. According to Lemmas 5 and 4, we have crL3J2>1. Thus, ξ1J2=3.
Using the analogous arguments, we haveξ1Ji=3 for 3≤i≤5.DefineWt1,t2 to be the graph obtained from J4 by subdividing the edges a1a2 and a2b2 to a path of length t1 and t2, respectively. Define Zt1,t2 to be the graph obtained by adding two new vertices v1 and v2 to Wt1,t2 and joining them to b2. These two families of graphs are depicted in Figure 5.Figure 5
The graphsWt1,t2 and Zt1,t2.
(a)(b)Lemma 14.
Whent1≥2 and t2≥1, we have ξ1Wt1,t2=4. When t1≥2 and t2≥2, we have ξ1Zt1,t2=4.Proof.
Firstly, we show thatξ1Wt1,t2=4 when t1≥2 and t2≥1. It is seen that, when t2=1, L3Wt1,t2 is a planar graph with two noncut-vertices of degree 4; when t2≥2, we have crL3Wt1,t2=1 and ΔL3Wt1,t2=5. This observation together with Lemmas 5 and 4 yields crL4Wt1,t2>1. By the definition, ξ1Wt1,t2=4.
Now, we prove thatξ1Zt1,t2=4 when t1≥2 and t2≥2. Note that L2Zt1,t2 is a planar graph with ΔL2Zt1,t2=4 and that L2Zt1,t2 has a unique noncut-vertex of degree 4, thus crL3Zt1,t2=1 by Lemma 4. Furthermore, since ΔL3Zt1,t2=5, it follows from Lemma 5 that crL4Zt1,t2>1. Consequently, ξ1Zt1,t2=4.Lemma 15.
ξ1Y2,2,2=3.Proof.
Observe thatL2Y2,2,2 is a planar graph with maximum degree 4; moreover, L2Y2,2,2 has at least two noncut-vertices of degree 4. Thus, by Lemma 4, crL3Y2,2,2>1. By the definition, ξ1Y2,2,2=3.Theorem 6.
For any graphG, ξ1G=4 if and only if G is one of the graphs Xtt≥3, Zt1,t2t1≥2,t2≥2, Wt1,t2t1≥2,t2≥1, Y1,1,t3t3≥3, or Y1,t2,t3t2≥2,t3≥2.Proof.
By Lemmas8, 12, and 14, if G is one of the graphs Xtt≥3, Zt1,t2t1≥2,t2≥2, Wt1,t2t1≥2,t2≥1, Y1,1,t3t3≥3, or Y1,t2,t3t2≥2,t3≥2, we obtain that ξ1G=4.
For the converse, letG be a graph with ξ1G=4. By Lemma 7 and Theorem 1, ΔG=3.Claim 4.
Each edge ofG is contained in at most one cycle; moreover, there is at most one cycle in G.Proof.
of Claim 4. If not, G contains a subgraph either isomorphic to J1 or to J2. By Lemmas 6 and 13, ξ1G≤3, a contradiction.By Claim4, we only need to consider the following two cases:Case 1.G is unicyclic.LetCtt≥3 be the unique cycle in G. Since ΔG=3, then at least one vertex of Ct has degree 3 in G. If there are at least two such vertices, then G contains J3 as a subgraph; hence, ξ1G≤ξ1J3=3 by Lemmas 6 and 13. This contradiction implies that, in Ct, there is exactly one vertex of degree 3 in G.As we mentioned above,G cannot contain J1 as a subgraph. By Lemma 8, G is the graph Xtt≥3.Case 2.G is a tree.By Lemmas6, 13, and 15, we claim the following.Claim 5.
G cannot contain a subgraph isomorphic to J4, J5, or to Y2,2,2.Claim 6.
InG, there are at most three vertices of degree 3.Proof.
of Claim 6. Suppose to contrary that there are at least four vertices of degree 3 in G. By Claim 5, these 3-degree vertices cannot be adjacent to each other; otherwise, G contains J4 as a subgraph. Since G cannot contain Y2,2,2 as a subgraph; therefore, the tree G with at least four vertices of degree 3 will contain J5 as a subgraph, a contradiction with Claim 5.Assuming that there are three vertices of degree 3 inG, by Claim 5 and by Lemma 14, G is the graph Zt1,t2t1≥2,t2≥2.Assume that there are two vertices of degree 3 inG, and then G is Wt1,t2t1≥2,t2≥1 by Lemma 14.Finally, assume that there is only one vertex of degree 3 inG; then, by Claim 5 and Lemma 12, G is either Y1,1,t3t3≥3 or Y1,t2,t3t2≥2,t3≥2. The proof is completed.



---

*Source: 5752806-2020-12-24.xml*