Strongly Spanning Trailable Graphs with Small Circumference and Hamilton-Connected Claw-Free Graphs
- PDF / 416,958 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 176 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
Strongly Spanning Trailable Graphs with Small Circumference and Hamilton-Connected Claw-Free Graphs Xia Liu1 • Liming Xiong2 • Hong-Jian Lai3 Received: 4 November 2019 / Revised: 14 August 2020 / Accepted: 18 August 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract A graph G is strongly spanning trailable if for any e1 ¼ u1 v1 ; e2 ¼ u2 v2 2 EðGÞ (possibly e1 ¼ e2 ), Gðe1 ; e2 Þ, which is obtained from G by replacing e1 by a path u1 ve1 v1 and by replacing e2 by a path u2 ve2 v2 , has a spanning ðve1 ; ve2 Þ-trail. A graph G is Hamilton-connected if there is a spanning path between any two vertices of V(G). In this paper, we first show that every 2-connected 3-edge-connected graph with circumference at most 8 is strongly spanning trailable with an exception of order 8. As applications, we prove that every 3-connected fK1;3 ; N1;2;4 g-free graph is Hamilton-connected and every 3-connected fK1;3 ; P10 g-free graph is Hamiltonconnected with a well-defined exception. The last two results extend the results in Hu and Zhang (Graphs Comb 32: 685–705, 2016) and Bian et al. (Graphs Comb 30: 1099–1122, 2014) respectively. Keywords Strongly spanning trailable Hamilton-connected Supereulerian Collapsible Reduction
& Liming Xiong [email protected] Xia Liu [email protected] Hong-Jian Lai [email protected] 1
School of Mathematics and Statistics, Beijing Institute of Technology, Beijing 100081, People’s Republic of China
2
School of Mathematics and Statistics, Beijing Key Laboratory on MCAACI, Beijing Institute of Technology, Beijing 100081, People’s Republic of China
3
Department of Mathematics, West Virginia University, Morgantown, WV 26506, USA
123
Graphs and Combinatorics
1 Introduction For the notation or terminology not defined here, see [2]. A graph is called trivial if it has only one vertex, non-trivial otherwise. An empty graph is one in which no two vertices are adjacent. For a connected graph G, we use jðGÞ, j0 ðGÞ, c(G) and g(G) to denote the connectivity, edge connectivity, circumference and girth of G, respectively. Throughout this paper, we use Pn , Cn to denote a path or a cycle of order n. The graph Ni;j;k is a triangle with disjoint paths of length i, j, k each attaching to distinct vertices of the triangle; Hi denotes the graph formed from two triangles, which are connected by a single path of length i. The graph Ni;j;k is defined but we are defining Bi;j = Ni;j;0 and Zi ¼ Ni;0;0 here. A graph G is Hamilton-connected if there is a spanning path between any pair vertices of V(G). For a collection H of graphs, graph G is said to be H-free if G does not contain H as an induced subgraph for all H 2 H (see [11]). Any Hamilton-connected graph is 3-connected. Then it is natural to consider which forbidden pairs of graphs fR; Sg imply that a 3-connected fR; Sg-free graph G is Hamilton-connected. Faudree and Gould in [10] showed that one of them must be K1;3 . We now list the known graphs S which, together with the K1;3 , imp
Data Loading...
