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

Jun Fujisawa; Liming Xiong; Kiyoshi Yoshimoto; Shenggui Zhang

doi:10.1002/jgt.20220

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

Jun Fujisawa^*, Liming Xiong, Kiyoshi Yoshimoto, Shenggui Zhang

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

13 Citations (Scopus)

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/8 components. For a simple graph with minimum degree at least three also, the same conclusion holds.

Original language	English
Pages (from-to)	72-82
Number of pages	11
Journal	Journal of Graph Theory
Volume	55
Issue number	1
DOIs	https://doi.org/10.1002/jgt.20220
Publication status	Published - May 2007

Keywords

2-factor
Line graph
Number of components

Access to Document

10.1002/jgt.20220

Cite this

@article{3bbd04b948884d988b0681ebc9524875,

title = "The upper bound of the number of cycles in a 2-factor of a line graph",

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/8 components. For a simple graph with minimum degree at least three also, the same conclusion holds.",

keywords = "2-factor, Line graph, Number of components",

author = "Jun Fujisawa and Liming Xiong and Kiyoshi Yoshimoto and Shenggui Zhang",

year = "2007",

month = may,

doi = "10.1002/jgt.20220",

language = "English",

volume = "55",

pages = "72--82",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

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

AU - Fujisawa, Jun

AU - Xiong, Liming

AU - Yoshimoto, Kiyoshi

AU - Zhang, Shenggui

PY - 2007/5

Y1 - 2007/5

N2 - 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/8 components. For a simple graph with minimum degree at least three also, the same conclusion holds.

AB - 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/8 components. For a simple graph with minimum degree at least three also, the same conclusion holds.

KW - 2-factor

KW - Line graph

KW - Number of components

UR - http://www.scopus.com/inward/record.url?scp=34248222564&partnerID=8YFLogxK

U2 - 10.1002/jgt.20220

DO - 10.1002/jgt.20220

M3 - Article

AN - SCOPUS:34248222564

SN - 0364-9024

VL - 55

SP - 72

EP - 82

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this