Supereulerian graphs with small circumference and 3-connected hamiltonian claw-free graphs

详细信息    查看全文

• 作者：Xiaoling Ma^a ; ^{mathmxl115@xju.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Hong-Jian Lai^a ; ^b ; ^{hongjianlai@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Wei Xiong^a ; ^{xingheng-1985@163.com" class="auth_mail" title="E-mail the corresponding author} ; Baoyingdureng Wu^a ; ^{baoyin@xju.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Xinhui An^a ; ^{xjaxh@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Hamiltonian graphs ; Forbidden subgraphs ; Claw-free graphs ; ZqZq-free graphs ; PkPk-free graphs ; Supereulerian graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 March 2016
• 年：2016
• 卷：202
• 期：Complete
• 页码：111-130
• 全文大小：628 K

文摘

A graph G$G$ is supereulerian if it has a spanning eulerian subgraph. We prove that every 3-edge-connected graph with the circumference at most 11 has a spanning eulerian subgraph if and only if it is not contractible to the Petersen graph. As applications, we determine collections F₁${\mathcal{F}}_1$, F₂${\mathcal{F}}_2$ and F₃${\mathcal{F}}_3$ of graphs to prove each of the following

(i) Every 3-connected {K_1,3,Z₉}$\{K_{1,3},Z_9\}$-free graph is hamiltonian if and only if its closure is not a line graph L(G)$L\left(G\right)$ for some G∈F₁$G\in {\mathcal{F}}_1$.

(ii) Every 3-connected {K_1,3,P₁₂}$\{K_{1,3},P_{12}\}$-free graph is hamiltonian if and only if its closure is not a line graph L(G)$L\left(G\right)$ for some G∈F₂$G\in {\mathcal{F}}_2$.

(iii) Every 3-connected {K_1,3,P₁₃}$\{K_{1,3},P_{13}\}$-free graph is hamiltonian if and only if its closure is not a line graph L(G)$L\left(G\right)$ for some G∈F₃$G\in {\mathcal{F}}_3$.