$$P_{3}$$ P 3 -Factors in the Square of a Tree
- PDF / 507,039 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 135 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
P3 -Factors in the Square of a Tree Guowei Dai1
•
Zhiquan Hu1
Received: 19 December 2019 / Revised: 19 December 2019 Springer Japan KK, part of Springer Nature 2020
Abstract A spanning subgraph H of a graph G is a P3 -factor of G if every component of H is a path of order three. The square of a graph G, denoted by G2 , is the graph with vertex set V(G) such that two vertices are adjacent in G2 if and only if their distance in G is at most 2. A graph G is subcubic if it has maximum degree at most three. In this paper, we give a sharp necessary condition for the existence of P3 -factors in the square of a tree, which improves a result of Li and Zhang (Graphs Combin 24:107– 111, 2008). In addition, we will also present a sufficient condition for the existence of P3 -factors in the square of a tree, which has the following interesting application to subcubic trees: if T is a subcubic tree of order 3n such that jLðT LðTÞÞj 7, then T 2 has a P3 -factor, where L(T) denotes the set of leaves in T. Examples show that the upper bound 7 on jLðT LðTÞÞj is sharp. Keywords Square graph Tree Path factor P3 -factor Subcubic
Mathematics Subject Classification (2000) 05C38 05C70
1 Introduction In this paper, we consider only finite simple graphs and refer to [5] for notation and terminologies not defined here. Let G be a graph. For u 2 VðGÞ, we denote by dG ðuÞ and NG ðuÞ the degree and the neighborhood of u in G, respectively. For X VðGÞ, Financially supported by NSFC Grants 11771172, 11871239, 11971196 and 11671164. & Guowei Dai [email protected] Zhiquan Hu [email protected] 1
Faculty of Mathematics and Statistics, Central China Normal University, Wuhan 430079, China
123
Graphs and Combinatorics
let G[X] be the subgraph of G induced by X and define G X :¼ G½VðGÞ X. A graph G is claw-free if there is no induced subgraph of G isomorphic to K1;3 . Let G be a graph. For x 2 VðGÞ, we use Gx to denote the component of G containing x. For x; y 2 VðGÞ with x 6¼ y, we use P[x, y] to denote a path P in G with end vertices x, y and assume that it has an orientation from x to y. For each v 2 Pðx; y and w 2 P½x; yÞ, let v and wþ be the predecessor of v and the successor of w on P, respectively. Define recursively vðkþ1Þ ¼ ðvk Þ ; vþðkþ1Þ ¼ ðvþk Þþ for k 1, if they exist. Let F be a family of connected graphs. A spanning subgraph H of a graph G is an F -factor of G if every component of H is isomorphic to some graph in F . For an integer k 2, we use Pk to denote a path of order k and P k the set of paths with order at least k. Thus, a P 3 -factor means a graph factor in which every component is a path of order at least three. For convenience, we call an F -factor of G a P3 factor if F ¼ fP3 g. Since Tutte proposed the well known Tutte 1-factor theorem [15], there are many results on graph factors [2, 3] and P k -factors in claw-free graphs and cubic graphs [4, 11, 12]. More results on graph factors are referred to the survey papers
Data Loading...
