The upper bound of the number of cycles in a 2‐factor of a line graph |
| |
Authors: | Jun Fujisawa Liming Xiong Kiyoshi Yoshimoto Shenggui Zhang |
| |
Institution: | 1. Department of Computer Science, Nihon University, Sakurajosui 3‐25‐40, Setagaya‐ku, Tokyo 156‐8550, Japan;2. Department of Mathematics, Beijing Institute of Technology, Beijing 100081, China;3. Department of Mathematics, College of Science and Technology, Nihon University, Tokyo 101‐8308, Japan;4. Department of Applied Mathematics, Northwestern Polytechnical University, Xian, Shaanxi 710072, China |
| |
Abstract: | Let G be a simple graph with order n and minimum degree at least two. In this paper, we prove that if every odd branch‐bond in G has an edge‐branch, then its line graph has a 2‐factor with at most components. For a simple graph with minimum degree at least three also, the same conclusion holds. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 72–82, 2007 |
| |
Keywords: | line graph 2‐factor number of components |
|
|