Removable ears of 1-extendable graphs

被引:0
作者
Shaohui Zhai
Xiaofeng Guo
机构
[1] Xiamen University of Technology,Department of Mathematics and Physics
[2] Xiamen University,School of Mathematical Sciences
来源
Journal of Systems Science and Complexity | 2010年 / 23卷
关键词
1-extendable graphs; removable ear; removable edge;
D O I
暂无
中图分类号
学科分类号
摘要
Carvalho, Lucchesi and Murty proved that any 1-extendable graph G different from K2 and C2n has at least Δ(G) edge-disjoint removable ears, and any brick G distinct from K4 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \overline {C_6 } $$\end{document} 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 K2 and C2n has at least χ′(G) edge-disjoint removable ears, and any brick G distinct from K4 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \overline {C_6 } $$\end{document} has at least χ′(G) − 2 removable edges, where χ′(G) denotes the edge-chromatic number of G.
引用
收藏
页码:372 / 378
页数:6
相关论文
共 10 条
  • [1] de Carvalho M. H.(1999)Ear decompositions of matching covered graphs Combinatorica 19 151-174
  • [2] Lucchesi C. L.(1980)On Discrete Math. 31 201-210
  • [3] Murty U. S. R.(1982)-extendable graphs Combinatorica 2 247-274
  • [4] Plummer M. D.(1987)Brick decomposition and the matching rand of graphs J. Combin. Theory Ser. B 43 187-222
  • [5] Edmonds J.(1983)Matching structure and the matching lattice Combinatorica 3 105-117
  • [6] Lovász L.(1988)Ear decompositions of matching covered graphs Congr. Numer. 63 147-160
  • [7] Pulleyblank W. R.(undefined)Matching extension and connectivity in graphs undefined undefined undefined-undefined
  • [8] Lovász L.(undefined)undefined undefined undefined undefined-undefined
  • [9] Lovász L.(undefined)undefined undefined undefined undefined-undefined
  • [10] Plummer M. D.(undefined)undefined undefined undefined undefined-undefined