Premium
Path factors of bipartite graphs
Author(s) -
Wang Hong
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180207
Subject(s) - bipartite graph , mathematics , combinatorics , path (computing) , complete bipartite graph , discrete mathematics , graph , computer science , computer network
A path on n vertices is denoted by P n . For any graph H , the number of isolated vertices of H is denoted by i(H) . Let G be a graph. A spanning subgraph F of G is called a { P 3 , P 4 , P 5 }‐factor of G if every component of F is one of P 3 , P 4 , and P 5 . In this paper, we prove that a bipartite graph G has a { P 3 , P 4 , P 5 }‐factor if and only if i(G − S − M) ≦ 2| S | + | M | for all S ⊆ V(G) and independent M ⊆ E(G) .