# The Existence of Spanning Ended System on Claw-Free Graphs

Authors: Xiaodong Chen; Meijin Xu; Yanjun Liu
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

We prove that every connected claw-free graphG contains a spanning k-ended system if and only if cl(G) contains a spanning k-ended system, where cl(G) denotes Ryjáček closure of G.


---

## Body

## 1. Introduction

Graph theory focuses on graphs composed of vertices and edges. The vertices in a graph are considered as discrete points usually discussed in control problems. Then there are a lot of results using graph theory to solve control and other application problems [1–13].We consider only finite and simple graphs. For notation and terminology not defined here we refer to [14]. For a subgraph H of a graph G, G-H denotes the induced subgraph by V(G)-V(H), and G[S] denotes the induced subgraph by S for S⊆V(G). For v∈V(G), let N(v) denote the set of vertices adjacent to v, and N[v]=N(v)∪{v}. P[a,b] denotes a path with end vertices a, b and a positive orientation from a to b. For a path P[a,b], x,y∈V(P), let xPy denote the subpath from x to y with positive orientation and yP-x denote the subpath from y to x with negative orientation. Similarly, for a cycle C with a given direction, we can define C[a,b], C-[a,b] with a,b∈V(C). In the paper, we define clockwise as the positive direction of a cycle. We use Km to denote a complete graph with order m, and if m=1, then it is trivial vertex. A tree with at most k leaves is called k-ended tree.A graph is calledclaw-free if it does not contain K1,3 induced subgraph. For a vertex x∈V(G), let Gx denote the graph with V(Gx)=V(G) and E(Gx)=E(G)∪{uv:u,v∈N(x)}, and then Gx is calledthe local completionof G at x. For a graph G, x∈V(G), if G[N(x)] is connected, then x islocally connected; if G[N(x)] is a complete induced subgraph of G, then x issimplicial; if x is locally connected, but not simplicial, then x iseligible.Ryjáček [15] proposed a closure operation on a claw-free graph G by joining all nonadjacent pairs of vertices in the neighbourhood of every eligible vertex till there is no eligible vertex, and then we get the closure cl(G). Ryjáček also gave the following result, which is considered a useful tool to research on the Hamiltonian properties of claw-free graphs.Theorem 1 (Ryjáček [15]).
IfG is a connected claw-free graph, then cl(G) is Hamiltonian if and only if G is Hamiltonian.
Actually, there are a lot of results which present thatcl(G) and G have many common properties.Theorem 2 (Brandt et al. [13]).
A claw-free graphG is traceable if and only if cl(G) is traceable.Theorem 3 (Ryjáček et al. [16]).
LetG be a claw-free graph. If cl(G) contains 2 factors with k components, then G contains 2 factors with at most k components.A tree with at mostk leaves is called k-ended tree. Win [17] provided sufficient conditions for a graph to contain spanning k-ended trees by spanning k-ended system. A system of a graph which contains paths, cycles, and trivial vertices is defined by a function f(α) as follows: (1)fα=1ifαisK1,K2,oracycle,2ifαisapathoforderatleast3.A systemS is called k-ended system if ∑α∈S‍f(α)≤k. Moreover, if V(S)=V(G), then S is called a spanning k-ended system of G. Obviously, if G contains a spanning k-ended system, then G contains a spanning k-ended tree. It follows that if a graph contains no spanning k-ended tree, then it contains no spanning k-ended systems.In this paper, we prove thatcl(G) can preserve the existence of spanning k-ended system of G.Theorem 4.
A claw-free graphG contains a spanning k-ended system if and only if cl(G) contains a spanning k-ended system.


## 2. Proof of Theorem4

We divide ak-ended system S of a graph G into two sets S1 and S2 and let(2)S1=α∈S:fα=1,S2=α∈S:fα=2.For every componentC∈S1, we take one vertex xC∈V(C). For every path P∈S2, let xP and yP denote the two end vertices of P. We define(3)EndS1=⋃C∈S1xC,EndS2=⋃P∈S2xP,yP,EndS=EndS1∪EndS2.For a spanningt-ended system S of a graph G, if there is no spanning s-ended system with s<t, then we call the systemminimum spanningt-ended system. Obviously, for a minimum spanning t-ended system S of G, End(S) is an independent set of G with EndS=t.In order to prove Theorem4, we only need to prove that the following result holds.Theorem 5.
LetG be a claw-free graph with δ(G)≥2. Then Gx contains a spanning k-ended system for any vertex x∈V(G) if and only if G contains a spanning k-ended system.Proof.
Obviously, the sufficiency holds and we only need to prove the necessity. AssumeGx contains a spanning k-ended system S which satisfies the following properties. (T1)
S is a minimum spanning k-ended system of Gx.(T2)
E(Gx)-E(G) is minimum, subject to (T1).(T3)
|S2| is minimum, subject to (T1) and (T2).(T4)
IfP contains x, then P contains as many vertices in N(x) as possible, where P∈S2 subject to (T1), (T2), and (T3).(T5)
IfC contains x, then C contains as many vertices in N(x) as possible, where C∈S1 subject to (T1), (T2), and (T3). If E(S)-E(G)=∅, then S is a spanning k-ended system in G, and we are done. Thus we assume |E(S)-E(G)|≥1.Claim 1.
ForP∈S2, if E(P)-E(G)≠∅, then x∈V(P).Proof.
To the contrary, supposex∉V(P), P=aPb, and uv∈E(P)-E(G) with v=u+. Then u,v∈N(x). Suppose x∈cP1d, P1∈S2. Since G[x,u,v,x+(x-)]≠K1,3, ux+(ux-)∈E(G) or vx+(vx-)∈E(G). Without loss of generality, suppose x≠d and ux+∈E(G). Then Gx contains two paths P2=cP1xvPb and P3=aPux+P1d. Replacing P and P1 by P2 and P3, then Gx contains a spanning k-ended system with less edge than E(Gx)-E(G), a contradiction to (T2).
Supposex∈V(C), C∈S1. If C={u}, then Gx contains a path P′=aPuxvPb with V(P′)=V(C)∪V(P). Replacing P and C by P′, Gx contains a spanning (k-1)-ended system, a contradiction to (T1). Thus VC≥2. Since G[x,u,v,x+]≠K1,3, ux+∈E(G) or vx+∈E(G). Without loss of generality, suppose ux+∈E(G). Then Gx contains a path P′=aPuC[x+,x]vPb with V(P′)=V(P)∪V(C). Replacing P and C by P′, then Gx contains a spanning (k-1)-ended system, a contradiction to (T1).Claim 2.
ForC∈S1, if E(C)-E(G)≠∅, then x∈V(C).Proof.
SinceE(C)-E(G)≠∅, |V(C)|≥2. Suppose uv∈E(C)-E(G), v=u+. Assume to the contrary x∉V(C). Suppose x∈aPb, P∈S2. Since G[x,x+(x-),u,v]≠K1,3, x+u(x-u)∈E(G) or x+v(x-v)∈E(G). Without loss of generality, assume x≠b and x+u∈E(G). Then Gx contains a path P′=bP-x+C-[u,v]xP-a with V(P′)=V(P)∪V(C). Replacing P, C by P′, then Gx contains a spanning (k-1)-ended system, a contradiction.
Supposex∈V(C′), C′∈S1-{C}. If V(C′)={x}, then Gx contains a cycle C′′=C[v,u]xv with V(C′′)=V(C)∪V(C′). Replacing C,C′ by C′′, then Gx contains a spanning (k-1)-ended system, a contradiction. If |VC′|≥2, then by the preceding proof x+u∈E(G) or x+v∈E(G). Without loss of generality, assume x+u∈E(G). Then Gx contains a cycle C′′=xCv,uC′[x+,x] with V(C′′)=V(C)∪V(C′). Replacing C, C′ by C′′, then Gx contains a spanning (k-1)-ended system, a contradiction.
SinceS is a disjoint system, we can get the following two results by Claims 1 and 2.Claim 3.
ForP∈S2, if E(P)-E(G)≠∅, then E(S)-E(G)⊆E(P).Claim 4.
ForC∈S1, if E(C)-E(G)≠∅, then E(S)-E(G)⊆E(C).
Now we prove the case thatE(P)-E(G)≠∅, for P∈S2. Then, by Claim 3, E(S)-E(G)⊆E(P). Suppose P=aPb, and then we can get the following results.Claim 5.
Consider the following:EP-EG≤2.Proof.
Suppose, to the contrary,u1v1,u2v2,u3v3∈E(P)-E(G), where u1, v1, u2, v2, u3, and v3 are labeled in order along the positive orientation of P. Since G[x,u1,v1, v2]≠K1,3, u1v2∈E(G) or v1v2∈E(G). Without loss of generality, assume u1v2∈E(G). Then Gx contains a path P′=aPu1v2Pu3v1Pu2v3Pb with V(P′)=V(P) and |EP′-E(G)|<|E(P)-E(G)|, a contradiction to (T2).Claim 6.
Consider the following:EP-EG=1.Proof.
Suppose, to the contrary,|E(P)-E(G)|=2 by Claim 5 and u1v1,u2v2∈E(P)-E(G), where u1, v1, u2, and v2 are labeled in order along the positive orientation of P. By the proof of Claim 5, u1v2,v1u2∈E(G), v1v2∉E(G). By Claim 1, x∈V(P). Assume x∈P[a,u1]. Then x+v1∉E(G); otherwise Gx contains a path P′=aPxu2P-v1x+Pu1v2Pb with V(P)=V(P′) and |E(P′)-E(G)|=1, a contradiction to (T2) by Claim 3. If x+v2∈E(G), then Gx contains a path P′=aPxu2P-v1u1P-x+v2Pb with V(P)=V(P′) and |E(P′)-E(G)|<|E(P)-E(G)|, a contradiction to (T2) by Claim 3. Thus G[x,x+,v1,v2]=K1,3, a contradiction. By similar proof, we can prove that Claim 6 holds if x∈P[v1,u2]∪P[v2,b].
By Claim6, we assume that E(P)-E(G)={u1v1}, where u1, v1 are labeled in order along the positive orientation of P, and without loss of generality assume x∈P[a,u1]. Since x is eligible, there exists at least one path in N(x) connecting u1 and v1. Suppose P0 is the shortest path in N(x) connecting u1 and v1. Since G is claw-free, 3≤VP0≤4. Assume y∈V(P0), u1y∈E(G).Claim 7.
Consider the following:y∈V(P).Proof.
To the contrary, supposey∈V(P′), where P′=P′[c,d]∈S2-{P}. If y=c, then Gx contains a path P1=aPu1yP′d and a path P2=v1Pb. Replacing P and P′ by P1 and P2, then Gx contains a spanning k-ended system with no edge in E(Gx)-E(G), a contradiction to (T2). Similarly, y≠d. Thus y∉{c,d}. If y-v1∈E(G), then Gx contains a path P1=aPu1yP′d and a path P2=cP′y-v1Pb. Replacing P and P′ by P1 and P2, Gx contains a spanning k-ended system S′ with E(Gx)-E(G)=∅, a contradiction to (T2). Thus y-v1∉E(G). Similarly, v1y+∉E(G). If y-y+∈E(G), then Gx contains a path P1=aPu1yv1Pb and a path P2=cP′y-y+P′d. Replacing P and P′ by P1 and P2, Gx contains a spanning k-ended system S′ with E(Gx)-E(G)⊆E(P1) such that P1 contains more vertices in N(x) than P, a contradiction to (T4). Thus y-y+∉E(G). yv1∉E(G); otherwise G[y,v1,y-,y+]=K1,3, a contradiction. x+v1∉E(G); otherwise Gx contains a path P1=aPxu1P-x+v1Pb with V(P)=V(P1) and E(P1)-E(G)=∅, a contradiction to (T2). Then x+y∈E(G) by G[x,x+,y,v1]≠K1,3. y-x+∈E(G) or y+x+∈E(G) by G[y,y-,y+,x+]≠K1,3 and y-y+∉E(G). If x+y-∈E(G), then Gx contains two paths P1=aPxv1Pb and P2=cP′y-x+Pu1yP′d. Replacing P and P′ by P1 and P2, Gx contains a spanning k-ended system with no edge in E(Gx)-E(G), a contradiction to (T2). If x+y+∈E(G), Gx contains two paths P1=aPxv1Pb and P2=cP′yu1P-x+y+P′d. Replacing P and P′ by P1 and P2, then Gx contains a spanning k-1-ended system, a contradiction. Using a similar proof, we can get a contradiction if y1∈V(C) with C∈S1. Thus y∈V(P).
By Claim1 without loss of generality, in the following proof, assume x∈P[a,u1). Then x+u1,x-v1∈E(G), x-x+,x-u1,x+v1∉E(G) since G is claw-free and by (T2).Claim 8.
Consider the following:v1y∉E(G).Proof.
To the contrary, supposev1y∈E(G). By Claim 7, without loss of generality, assume y∈P[a,u1]. If y=a, then, replacing P by P1=u1P-yv1Pb, Gx contains a spanning k-ended system with no edge in E(Gx)-E(G), a contradiction to (T2). Thus y≠a. If y-u1∈E(G), then, replacing P by P1=aPy-u1P-yv1Pb, Gx contains a spanning k-ended system with no edge in E(Gx)-E(G), a contradiction to (T2). Similarly, y-y+∉E(G). By G[y,y-,y+,u1]≠K1,3, y+u1∈E(G). By G[y,y-,y+,x]≠K1,3, y-x∈E(G) or y+x∈E(G). If y-x∈E(G), then, replacing P by P1=aPxy-P-x+u1P-yv1Pb, Gx contains a spanning k-ended system with no edge in E(Gx)-E(G), a contradiction to (T2). Thus y+x∈E(G). Replacing P by path P1=aPxy+Pux+PyvPb, Gx contains a spanning k-ended system with no edge in E(Gx)-E(G), a contradiction to (T2).Claim 9.
P can be transformed to a path P1 such that V(P1)=V(P), v1y∈E(P1), and E(Gx)-E(G)={v1y}.Proof.
By Claim7, without loss of generality, assume y∈P(x,u1). Since G[y,y-,y+,x]≠K1,3, y-y+,y-x,y+x∈E(G). If y-y+∈E(G), then P1=aPy-y+Pu1yv1Pb. If y-x∈E(G), then P1=aPxy-P-x+u1P-yv1Pb. If y+x∈E(G), then P1=aPxy+Pu1x+Pyv1Pb.
By Claim8, v1y∉E(G), and then VP0=4. Suppose P0=u1yzv1. By Claim 9, replace P by P1. By the proof of Claim 7, z∈P1. By the proof of Claim 9, Gx contains a spanning k-ended system with no edge in E(Gx)-E(G), a contradiction to (T2). It follows that Theorem 4 holds and then Theorem 5 holds.



---

*Source: 6041841-2016-09-20.xml*