✦ LIBER ✦

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

✍ Scribed by Jun Fujisawa; Liming Xiong; Kiyoshi Yoshimoto; Shenggui Zhang

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 183 KB
Volume: 55
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20220

No coin nor oath required. For personal study only.

✦ Synopsis

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 least three also, the same conclusion holds. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 72–82, 2007

📜 SIMILAR VOLUMES

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 2 views

An upper bound for the harmonious chroma

An upper bound for the harmonious chromatic number of a graph

✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 1 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o

An upper bound for the k-domination numb

An upper bound for the k-domination number of a graph

✍ E. J. Cockayne; B. Gamble; B. Shepherd 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 1 views

The kdomination number of a graph G, y k ( G ) , is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k. then YAG) 5 kp/(k + 1).

On an upper bound for the harmonious chr

On an upper bound for the harmonious chromatic number of a graph

✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 1 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

A new upper bound for the independence n

A new upper bound for the independence number of edge chromatic critical graphs

✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 1 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley