✦ LIBER ✦

2-factors with the bounded number of components in line graphs

✍ Scribed by Liming Xiong

Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 210 KB
Volume: 24
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2010.12.018

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple graph of order n such that every vertex of degree 1 is adjacent to a vertex of degree at least 3. In this work, we prove that the line graph L(G) has a 2-factor with at most n-1 3 components if every odd branch-bond of G has a shortest branch of length 2. This is a best possible result which can be thought of as a counterpart of the main result in Fujisawa et al. (2007) [8].

📜 SIMILAR VOLUMES

The upper bound of the number of cycles

The upper bound of the number of cycles in a 2-factor of a line graph

✍ Jun Fujisawa; Liming Xiong; Kiyoshi Yoshimoto; Shenggui Zhang 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 2 views

## 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 ${{3n - 2}\over {8}}$ components. For a simple graph with minimum degree at le

On the structure of graphs with bounded

On the structure of graphs with bounded asteroidal number

✍ T. Kloks; D. Kratsch; H. Müller 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 13 KB

The number of cycles in 2-factors of cub

The number of cycles in 2-factors of cubic graphs

✍ Moshe Rosenfeld 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 758 KB

Graphs embedded in the plane with a boun

Graphs embedded in the plane with a bounded number of accumulation points

✍ C. Paul Bonnington; R. Bruce Richter 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## Abstract Halin's Theorem characterizes those infinite connected graphs that have an embedding in the plane with no accumulation points, by exhibiting the list of excluded subgraphs. We generalize this by obtaining a similar characterization of which infinite connected graphs have an embedding in

The number of 1-factors in 2k-connected

The number of 1-factors in 2k-connected graphs

✍ Béla Bollobas 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 166 KB

The maximum number of edges in 2K2-free

The maximum number of edges in 2K2-free graphs of bounded degree

✍ F.R.K. Chung; A. Gyárfás; Z. Tuza; W.T. Trotter 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 481 KB

A graph is 2K,-free if it does not contain an independent pair of edges as an induced subgraph. We show that if G is 2K,-free and has maximum degree A(G) = D, then G has at most 5D2/4 edges if D is even. If D is odd, this bound can be improved to (5D\* -20 + 1)/4. The extremal graphs are unique.