REMOVABLE EARS OF 1-EXTENDABLE GRAPHS

Shaohui ZHAI; Xiaofeng GUO

doi:10.1007/s11424-010-7122-0

PDF(204 KB)

系统科学与复杂性(英文) ›› 2010, Vol. 23 ›› Issue (2) : 372-378. DOI: 10.1007/s11424-010-7122-0

论文

REMOVABLE EARS OF 1-EXTENDABLE GRAPHS

Shaohui ZHAI(1), Xiaofeng GUO(2)

作者信息 +

REMOVABLE EARS OF 1-EXTENDABLE GRAPHS

Shaohui ZHAI(1), Xiaofeng GUO(2)

Author information +

文章历史 +

摘要

Carvalho, Lucchesi and Murty proved that any 1-extendable graph

G

different from

K_{2}

and

C_{2 n}

has at least

Δ (G)

edge-disjoint removable ears, and any brick

G

distinct from

K_{4}

and

\bar{C_{6}}

has at least

Δ (G) - 2

removable edges,
where

Δ (G)

denotes the maximum degree of

G

. In this paper,
we improve the lower bounds for numbers of removable ears and
removable edges of 1-extendable graphs. It is proved that any
1-extendable graph

G

different from

K_{2}

and

C_{2 n}

has at
least

χ^{'} (G)

edge-disjoint removable ears, and any brick

G

distinct from

K_{4}

and

\bar{C_{6}}

has at least

χ^{'} (G) - 2

removable edges, where

χ^{'} (G)

denotes the edge-chromatic number
of

G

Abstract

Carvalho, Lucchesi and Murty proved that any 1-extendable graph

G

different from

K_{2}

and

C_{2 n}

has at least

Δ (G)

edge-disjoint removable ears, and any brick

G

distinct from

K_{4}

and

\bar{C_{6}}

has at least

Δ (G) - 2

removable edges,
where

Δ (G)

denotes the maximum degree of

G

. In this paper,
we improve the lower bounds for numbers of removable ears and
removable edges of 1-extendable graphs. It is proved that any
1-extendable graph

G

different from

K_{2}

and

C_{2 n}

has at
least

χ^{'} (G)

edge-disjoint removable ears, and any brick

G

distinct from

K_{4}

and

\bar{C_{6}}

has at least

χ^{'} (G) - 2

removable edges, where

χ^{'} (G)

denotes the edge-chromatic number
of

G

导出引用

Shaohui ZHAI , Xiaofeng GUO. REMOVABLE EARS OF 1-EXTENDABLE GRAPHS. 系统科学与复杂性(英文), 2010, 23(2): 372-378 https://doi.org/10.1007/s11424-010-7122-0

Shaohui ZHAI , Xiaofeng GUO. REMOVABLE EARS OF 1-EXTENDABLE GRAPHS. Journal of Systems Science and Complexity, 2010, 23(2): 372-378 https://doi.org/10.1007/s11424-010-7122-0

PDF(204 KB)

Accesses

Citation

Detail

段落导航

摘要
Abstract
关键词
Key words
引用本文

收稿日期	修回日期	出版日期
2007-06-21	1900-01-01	2010-04-25
发布日期
2010-04-25

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

{{custom_fnGroup.title_cn}}

脚注

扫码分享

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

{{custom_fnGroup.title_cn}}

脚注