Supereulerian graphs with width and -collapsible graphs

详细信息    查看全文

• 作者：Ping Li^a ; ^{pingli@bjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Hao Li^b ; ^{lihao1982@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Ye Chen^c ; ^{yechent@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Herbert Fleischner^d ; ^{fleisch@dbai.tuwien.ac.at" class="auth_mail" title="E-mail the corresponding author} ; Hong-Jian Lai^e ; ^{hongjianlai@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Supereulerian graphs ; Collapsible graphs ; Edge-connectivity ; Edge-disjoint trails ; Supereulerian graphs with width ss ; The supereulerian width of a graph ; ss-collapsible graphs ; Eulerian-connected graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 February 2016
• 年：2016
• 卷：200
• 期：Complete
• 页码：79-94
• 全文大小：584 K

文摘

For an integer i42" class="mathmlsrc">i42.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=88bdedf1499c75f49cb01da4bd43fc04" title="Click to view the MathML source">s>0 and for i43" class="mathmlsrc">i43.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=dcfcf2bff3a8d33aed8fa5e6b5987e52" title="Click to view the MathML source">u,v∈V(G) with i44" class="mathmlsrc">i44.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=dae0b0f001ee30f0e4a02805c9b7314e" title="Click to view the MathML source">u≠v, an i45" class="mathmlsrc">i45.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=aee3b2521fafc68d7611d77b0995d087" title="Click to view the MathML source">(s;u,v)-trail-system of G$G$ is a subgraph i47" class="mathmlsrc">i47.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=743712e4ec7336c8b737589e4fc57543" title="Click to view the MathML source">H consisting of i40" class="mathmlsrc">i40.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=07fa5bae522aa1ecb2b0e7b1d2fac8e1" title="Click to view the MathML source">s edge-disjoint i49" class="mathmlsrc">i49.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=664285af6f63f91c631f0066a979ec86" title="Click to view the MathML source">(u,v)-trails. A graph is supereulerian with widthi40" class="mathmlsrc">i40.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=07fa5bae522aa1ecb2b0e7b1d2fac8e1" title="Click to view the MathML source">s if for any i43" class="mathmlsrc">i43.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=dcfcf2bff3a8d33aed8fa5e6b5987e52" title="Click to view the MathML source">u,v∈V(G) with i44" class="mathmlsrc">i44.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=dae0b0f001ee30f0e4a02805c9b7314e" title="Click to view the MathML source">u≠v, G$G$ has a spanning i45" class="mathmlsrc">i45.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=aee3b2521fafc68d7611d77b0995d087" title="Click to view the MathML source">(s;u,v)-trail-system. The supereulerian width489d83f8b0a" title="Click to view the MathML source">μ^′(G)${\mu }^{\prime }\left(G\right)$ of a graph G$G$ is the largest integer i40" class="mathmlsrc">i40.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=07fa5bae522aa1ecb2b0e7b1d2fac8e1" title="Click to view the MathML source">s such that G$G$ is supereulerian with width k$k$ for every integer k$k$ with 0≤k≤s$0\le k\le s$. Thus a graph G$G$ with μ^′(G)≥2${\mu }^{\prime }\left(G\right)\ge 2$ has a spanning Eulerian subgraph. Catlin (1988) introduced collapsible graphs to study graphs with spanning Eulerian subgraphs, and showed that every collapsible graph G$G$ satisfies μ^′(G)≥2${\mu }^{\prime }\left(G\right)\ge 2$ (Catlin, 1988; Lai et al., 2009). Graphs G$G$ with μ^′(G)≥2${\mu }^{\prime }\left(G\right)\ge 2$ have also been investigated by Luo et al. (2006) as Eulerian-connected graphs. In this paper, we extend collapsible graphs to i40" class="mathmlsrc">i40.gif&_user=111111111&_pii=S0166218X15003546&_rdoc=1&_issn=0166218X&md5=07fa5bae522aa1ecb2b0e7b1d2fac8e1" title="Click to view the MathML source">s-collapsible graphs and develop a new related reduction method to study 489d83f8b0a" title="Click to view the MathML source">μ^′(G)${\mu }^{\prime }\left(G\right)$ for a graph G$G$. In particular, we prove that K_3,3$K_{3,3}$ is the smallest 3-edge-connected graph with μ^′<3${\mu }^{\prime }<3$. These results and the reduction method will be applied to determine a best possible degree condition for graphs with supereulerian width at least 3, which extends former results in Catlin (1988) and Lai (1988).