Degree conditions for the existence of a {<i>P</i><sub>2</sub>, <i>P</i><sub>5</sub>}-factor in a graph
Sufang Wang, Wei Zhang
Abstract
A subgraph of a graph G is spanning if the subgraph covers all vertices of G. A path- factor of a graph G is a spanning subgraph H of G such that every component of H is a path. In this article, we prove that (i) a connected graph G with δ ( G ) ≥ 5 admits a { P 2 , P 5 }-factor if G satisfies δ( G ) > 3α( G )-1/4; (ii) a connected graph G of order n with n ≥ 7 has a { P 2 , P 5 }-factor if G satisfies max{ d G ( x ) , d G ( y )} ≥ 3 n /7 for any two nonadjacent vertices x and y of G.
Topics & Concepts
CombinatoricsMathematicsGraphGraph factorizationBound graphFactor-critical graphPath graphDiscrete mathematicsGraph powerInduced subgraphPath (computing)Line graphVertex (graph theory)Computer scienceProgramming languageAdvanced Graph Theory ResearchGraph theory and applicationsgraph theory and CDMA systems