We introduce a closure technique for Hamilton-connectedness of {K1,3,Γ3}-free graphs, where Γ3 is the graph obtained by joining two vertex-disjoint triangles with a path of length 3. The closure ...turns a claw-free graph into a line graph of a multigraph while preserving its (non)-Hamilton-connectedness. The most technical parts of the proof are computer-assisted.
The main application of the closure is given in a subsequent paper showing that every 3-connected {K1,3,Γ3}-free graph is Hamilton-connected, thus resolving one of the two last open cases in the characterization of pairs of connected forbidden subgraphs implying Hamilton-connectedness.
In the first one in this series of two papers, we have proved that every 3‐connected {
K
1
,
3
,
N
1
,
3
,
3
} $\{{K}_{1,3},{N}_{1,3,3}\}$‐free graph is Hamilton‐connected. In this paper, we continue ...in this direction by proving that every 3‐connected {
K
1
,
3
,
X
} $\{{K}_{1,3},X\}$‐free graph, where X
∈
{
N
1
,
1
,
5
,
N
2
,
2
,
3
} $X\in \{{N}_{1,1,5},{N}_{2,2,3}\}$, is Hamilton‐connected (where N
i
,
j
,
k ${N}_{i,j,k}$ is the graph obtained by attaching endvertices of three paths of lengths i
,
j
,
k $i,j,k$ to a triangle). This together with a previous result of other authors completes the characterization of forbidden induced generalized nets implying Hamilton‐connectedness of a 3‐connected claw‐free graph. We also discuss remaining open cases in a full characterization of connected graphs X $X$ such that every 3‐connected {
K
1
,
3
,
X
} $\{{K}_{1,3},X\}$‐free graph is Hamilton‐connected.
On s-hamiltonicity of net-free line graphs Ma, Xiaoling; Wu, Yang; Zhan, Mingquan ...
Discrete mathematics,
January 2021, 2021-01-00, Letnik:
344, Številka:
1
Journal Article
Recenzirano
For integers s1,s2,s3>0, let Ns1,s2,s3 denote the graph obtained by identifying each vertex of a K3 with an end vertex of three disjoint paths Ps1+1, Ps2+1, Ps3+1 of length s1,s2 and s3, ...respectively. We prove the following results.
(i) Let N1={Ns1,s2,s3:s1>0,s1≥s2≥s3≥0 and s1+s2+s3≤6}. Then for any N∈N1, every N-free line graph L(G) with |V(L(G))|≥s+3 is s-hamiltonian if and only if κ(L(G))≥s+2.
(ii) Let N2={Ns1,s2,s3:s1>0,s1≥s2≥s3≥0 and s1+s2+s3≤4}. Then for any N∈N2, every N-free line graph L(G) with |V(L(G))|≥s+3 is s-Hamilton-connected if and only if κ(L(G))≥s+3.
In 2016, McDiarmid and Yolov gave a tight threshold for the existence of Hamilton cycle in graphs with large minimum degree and without large “bipartite hole”(two disjoint sets of vertices with no ...edge between them) which extends Dirac's classical Theorem. In detail, an (s,t)-bipartite-hole in a graph G consists of two disjoint vertex sets S and T with |S|=s and |T|=t such that E(GS,T)=∅. Let α˜(G) be the maximum integer such that G contains an (s,t)-bipartite-hole for every pair of nonnegative integers s and t with s+t=r. Motivated by Bondy's metaconjecture, in this paper, we study the existence of vertex-pancyclicity (every vertex is in a cycle of length i for each i∈3,n and Hamilton-connectivity(any two vertices can be connected through a Hamilton path). Our central theorem is that for any given μ>0 and sufficiently large n, if G is an n-vertex graph with α˜(G)=μn and δ(G)≥103μn, then G is Hamilton-connected and vertex-pancyclic.
A graph G is called （k1,k2)-Hamilton-connected, if for any two vertex disjoint subsets X ={x1,x2,...,xk1} and U ={u1,u2,...,uk2}, G contains a spanning family F of k1k2 internally vertex disjoint ...paths such that for 1≤i≤k1 and 1≤j≤k2, F contains an xiuj path. Let σ2(G) be the minimum value of deg(u)+deg(v) over all pairs {u,v} of non-adjacent vertices in G . In this paper, we prove that an n-vertex graph is （2,k)-Hamilton-connected if is (5k-4)-connected with σ2(G) ≥ n+k-2 where k ≥2. We also prove that if σ2(G) ≥ n+k1k2-2 with k1,k2 ≥2., then G is （k1,k2)-Hamilton-connected. Moreover, these requirements of σ2 are tight.
An hourglassΓ0 is the graph with degree sequence (4, 2, 2, 2, 2) and a claw is the bipartite complete graph K1,3. In this paper, we show that(1)every 3-connected, essentially 4-connected ...{K1,3,Γ0}-free graph is Hamilton-connected,(2)every 3-connected {K1,3,Γ0,P16}-free graph is Hamilton-connected, where (1) improves similar results of (Li et al. (2008) 11) and hence (Broersma et al. (2001) 4); (2) settles one conjecture posed in (Ryjáček et al. (2018) 18).
For an integer i≥1, Zi is the graph obtained by attaching an endvertex of a path of length i to a vertex of a triangle. We prove that every 3-connected {K1,3,Z7}-free graph is Hamilton-connected, ...with one exceptional graph. The result is sharp.
A graph G is Hamilton-connected if for any pair of vertices v and w, G has a spanning (v, w)-path. Extending theorems of Dirac and Ore, Erdős prove a sufficient condition in terms of minimum degree ...and the size of G to assure G to be Hamiltonian. We investigate the spectral analogous of Erdős’ theorem for a Hamilton-connected graph with given minimum degree, and prove that there exist two graphs {Lnk,Mnk} such that each of the following holds for an integer k ≥ 3 and a simple graph G on n vertices.
(i) If n ≥ 6k, δ(G) ≥ k, and |E(G)|>(n−k2)+k(k+1), then G is Hamilton-connected if and only if Cn+1(G)∉{Lnk,Mnk}.
(ii) If n≥max{6k,12k3−12k2+k+4},δ(G) ≥ k and spectral radius λ(G)≥n−k, then G is Hamilton–connected if and only if G∉{Lnk,Mnk}.
Extending Cycles Locally to Hamilton Cycles Hamann, Matthias; Lehner, Florian; Pott, Julian
The Electronic journal of combinatorics,
03/2016, Letnik:
23, Številka:
1
Journal Article
Recenzirano
Odprti dostop
A Hamilton circle in an infinite graph is a homeomorphic copy of the unit circle $S^1$ that contains all vertices and all ends precisely once. We prove that every connected, locally connected, ...locally finite, claw-free graph has such a Hamilton circle, extending a result of Oberly and Sumner to infinite graphs. Furthermore, we show that such graphs are Hamilton-connected if and only if they are $3$-connected, extending a result of Asratian. Hamilton-connected means that between any two vertices there is a Hamilton arc, a homeomorphic copy of the unit interval $0,1$ that contains all vertices and all ends precisely once.
PDF