✦ LIBER ✦

Path factors of bipartite graphs

✍ Scribed by Hong Wang

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 375 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180207

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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).

📜 SIMILAR VOLUMES

Line graphs of bipartite graphs with Ham

Line graphs of bipartite graphs with Hamiltonian paths

✍ Francis K. Bell 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

It is shown that, if t is an integer !3 and not equal to 7 or 8, then there is a unique maximal graph having the path P t as a star complement for the eigenvalue À2: The maximal graph is the line graph of K m,m if t ¼ 2mÀ1, and of K m,m þ1 if t ¼ 2m. This result yields a characterization of L(G ) wh

On 2-factors of a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2-factor with exactly k components? We will prove that if , then, for any bipartite graph H = (U 1 , U 2 ; F ) with |U 1 | ≤ n, |U 2 | ≤ n and ∆(H) ≤ 2, G contains a subgraph i

Longest paths and cycles in bipartite or

Longest paths and cycles in bipartite oriented graphs

✍ Zhang Ke Min 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB 👁 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without

Path factors in cubic graphs

✍ Ken-ichi Kawarabayashi; Haruhide Matsuda; Yoshiaki Oda; Katsuhiro Ota 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB

Counting 1-Factors in Regular Bipartite

Counting 1-Factors in Regular Bipartite Graphs

✍ Alexander Schrijver 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 325 KB

We show that any k-regular bipartite graph with 2n vertices has at least \ (k&1) k&1 k k&2 + n perfect matchings (1-factors). Equivalently, this is a lower bound on the permanent of any nonnegative integer n\_n matrix with each row and column sum equal to k. For any k, the base (k&1) k&1 Âk k&2 is l

Solution of fink & straight conjecture o

Solution of fink & straight conjecture on path-perfect complete bipartite graphs

✍ Weiting Cao; Peter Hamburger 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

## Abstract We consider various edge disjoint partitions of complete bipartite graphs. One case is where we decompose the edge set into edge disjoint paths of increasing lengths. A graph __G__ is __path‐perfect__ if there is a positive integer __n__ such that the edge set __E__(__G__) of the graph