Supereulerian regular matroids without small cocircuits期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Supereulerian regular matroids without small cocircuits

Authors:	Bofeng Huo Qingsong Du Ping Li Yang Wu Jun Yin Hong-Jian Lai

Affiliation:	1. College of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai, People's Republic of China The State Key Laboratory of Tibetan Intelligent Information Processing and Application, Xining, Qinghai, People's Republic of China;2. Department of Mathematics, Beijing Jiaotong University, Beijing, People's Republic of China;3. Faculty of Information Technology, Macau University of Science and Technology, Macau, People's Republic of China;4. The State Key Laboratory of Tibetan Intelligent Information Processing and Application, Xining, Qinghai, People's Republic of China School of Computer, Qinghai Normal University, Xining, Qinghai, People's Republic of China;5. Department of Mathematics, West Virginia University, Morgantown, West Virginia, USA

Abstract:	A cycle of a matroid is a disjoint union of circuits. A matroid is supereulerian if it contains a spanning cycle. To answer an open problem of Bauer in 1985, Catlin proved in [J. Graph Theory 12 (1988) 29–44] that for sufficiently large $n $n$$ , every 2-edge-connected simple graph $G $G$$ with $◂=▸ n = ∣ V (G) ∣ $n=\| V(G)\| $$ and minimum degree $◂≥▸ δ (G) \geq \frac{n}{5} $delta (G)ge frac{n}{5}$$ is supereulerian. In [Eur. J. Combinatorics, 33 (2012), 1765–1776], it is shown that for any connected simple regular matroid $M $M$$ , if every cocircuit $D $D$$ of $M $M$$ satisfies $◂≥▸ ∣ D ∣ \geq \max {\frac{◂−▸ r (M) - 5}{5}, 6} $\| D\| ge max left{frac{r(M)-5}{5},6right}$$ , then $M $M$$ is supereulerian. We prove the following. (i) Let $M $M$$ be a connected simple regular matroid. If every cocircuit $D $D$$ of $M $M$$ satisfies $◂≥▸ ∣ D ∣ \geq \max {\frac{◂+▸ r (M) + 1}{10}, 9} $\| D\| ge max left{frac{r(M)+1}{10},9right}$$ , then $M $M$$ is supereulerian. (ii) For any real number $c $c$$ with $0 < c < 1 $0lt clt 1$$ , there exists an integer $f (c) $f(c)$$ such that if every cocircuit $D $D$$ of a connected simple cographic matroid $M $M$$ satisfies $∣ D ∣ \geq ◂lim▸ \max ◂{}▸ {c ◂()▸ (r (M) + 1), f (c)} $\| D\| ge max {c(r(M)+1),f(c)}$$ , then $M $M$$ is supereulerian.

Keywords:	contractible restrictions disjoint bases of matroids fractional arboricity of a matroid spanning cycles strength of a matroid supereulerian graphs

设为首页 | 免责声明 | 关于勤云 | 加入收藏