| 余爱梅,马仁森,王可可,孔将旭.C2(4,k) 中的强支撑可迹图[J].数学年刊A辑,2018,39(1):53~62 |
| C2(4,k) 中的强支撑可迹图 |
| Strongly Spanning Trailable Graphs in Graph Family C2(4,k) |
| Received:July 23, 2015 Revised:January 17, 2017 |
| DOI：10.16205/j.cnki.cama.2018.0006 |
| 中文关键词: 强支撑可迹图, 可折叠图, 简化图 |
| 英文关键词:Strongly spanning trailable graphs, Collapsible graphs, Reduction |
| 基金项目:本文受到国家自然科学基金 (No.11371193, No.11701541), 北京交通大学基本科研业务费(No.2015JB M107),
北京高等学校青年英才计划项目 (No.YETP0573), 高等学校学科创新引智计划(No.B16002)和浙江省自然科学基金(No.LQ17A010005)的资助. |
| Author Name | Affiliation | E-mail | | YU Aim | Department of Mathematics, Beijing Jiaotong
University, Beijing 100044, China. | yuaimeimath@163.com | | MA Rens | Department of Mathematics, Beijing Jiaotong
University, Beijing 100044, China. | 14121548@bjtu.edu.cn | | WANG Ke | Department of Mathematics, Embry-Riddle Aeronautical University, Precott, Arizona 86301, USA. | wangkk87@gmail.com | | KONG Jiang | School of Sciences, China Jiliang University, Hangzhou 310018, China. | kongjiangxu@163.com |
|
| Hits: 757 |
| Download times: 1334 |
| 中文摘要: |
| 设$2\leq h \leq 3$, $l>0$, $k \geq 0$是整数, $C_h(l, k)$是由$h${-}边连通简单图组成的集合.
图$G\in C_h(l, k)$当且仅当对图$G$的任意一个二边割或三边割$X$, 图$G-X$的每个分支都至少有
$\frac{|V(G)|- k}{l}$个点. 设$e=u_1v_1$和$e'=u_2v_2$是图$G$的两条边. 若$e \neq e'$, $G(e, e')$
是将图$G$中的边$e=u_1v_1$和$e'=u_2v_2$分别用路$u_1v_ev_1$和$u_2v_{e'}v_2$替换得到的图
(其中, $v_e, v_{e'}$是不在$V(G)$中的两个新的点). 若$e = e'$, $G(e, e')$是将图$G$中的边
$e=u_1v_1$用路$u_1v_ev_1$ 替换得到的图,也记作$G(e)$. 若对任意的$e, e' \in E(G)$,
$G(e, e')$ 都有支撑$(v_e, v_{e'})${-}迹, 则称图$G$是强支撑可迹的. 作者证明了, 若图
$G\in C_2(4,k)$且$|V(G)|> 5k$, 则要么图$G$是强支撑可迹图, 要么存在$e,e'\in E(G)$,
使得$G(e,e')$可以收缩成一个有限图类$\mathcal{F}$中的图. 当$k=4$时, $\mathcal{F}$被完全确定了. |
| 英文摘要: |
| For integers $h$, $l$ and $k$ with $2\leq h \leq 3$, $l>0$ and $k \geq 0$, let $C_h(l, k)$
denote the family of $h$-edge-connected simple graphs such that $G\in C_h(l, k)$ if and only
if for every edge cut $X\subseteq E(G)$ with size $2$ or $3$, each component of $G-X$ has at
least $\frac{|V(G)|- k}{l}$ vertices. Suppose that $e=u_1v_1$ and $e'=u_2v_2$ are two edges of $G$.
If $e \neq e'$, then $G(e, e')$ is the graph obtained from $G$ by replacing $e=u_1v_1$ with a
path $u_1v_ev_1$ and by replacing $e'=u_2v_2$ with a path $u_2v_{e'}v_2$, where $v_e, v_{e'}$
are two new vertices being not in $V(G)$. If $e = e'$, then $G(e, e')$, also denoted by $G(e)$, is
obtained from $G$ by replacing $e=u_1v_1$ with a path $u_1v_ev_1$. A graph $G$ is strongly
spanning trailable if for any $e, e' \in E(G)$, $G(e, e')$ has a spanning $(v_e, v_{e'})$-trail.
The authors prove that if $G\in C_2(4,k)$ and $|V(G)|> 5k$, either $G$ is strongly spanning trailable, or
there exist $e,e'\in E(G)$ such that $G(e,e')$ is contractible to a member in a finite family
$\mathcal{F}$. When $k=4$, $\mathcal{F}$ is determined. |
| View Full Text View/Add Comment Download reader |
| Close |
|
|
|
|
|
