𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs

✍ Scribed by Hajo Broersma; Daniël Paulusma; Kiyoshi Yoshimoto

Publisher
Springer Japan
Year
2009
Tongue
English
Weight
617 KB
Volume
25
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

2-factors with the bounded number of com
2-factors with the bounded number of components in line graphs
✍ Liming Xiong 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 210 KB

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 re

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

A sharp upper bound for the number of st
A sharp upper bound for the number of stable sets in graphs with given number of cut edges
✍ Hongbo Hua 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 648 KB

Let G be a connected and simple graph, and let i(G) denote the number of stable sets in G. In this letter, we have presented a sharp upper bound for the i(G)-value among the set of graphs with k cut edges for all possible values of k, and characterized the corresponding extremal graphs as well.

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.