In this paper,we give some sufficient conditions for a graph to be traceable in terms of its order and size.As applications,the normalized Laplacian spectral conditions for a graph to be traceable are established.
A traceable graph is a graph containing a Hamilton path.Let N[v]=N(v)∪{v}and J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.A graph G is cal_∑led quasi-claw-free if J(u,v)≠=?for any u,v∈V(G)with distance of two.Letσ_k(G...A traceable graph is a graph containing a Hamilton path.Let N[v]=N(v)∪{v}and J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.A graph G is cal_∑led quasi-claw-free if J(u,v)≠=?for any u,v∈V(G)with distance of two.Letσ_k(G)=min{∑_(v∈S)d(v):S is an independent set of V(G)with|S|=k},where d(v)denotes the degree of v in G.In this paper,we prove that if G is a connected quasi-claw-free graph of order n andσ_3(G)≥n-2,then G is traceable;moreover,we give an example to show the bound in our result is best possible.We obtain that if G is a connected quasi-claw-free graph of order n andσ_(2)(G)≥_(3)^(2(n-2)),then G is traceable.展开更多
基金Supported by the National Natural Science Foundation of China(Grant Nos.11961041,12261055)the Natural Science Foundation of Gansu Province(Grant No.21JR11RA065)。
文摘In this paper,we give some sufficient conditions for a graph to be traceable in terms of its order and size.As applications,the normalized Laplacian spectral conditions for a graph to be traceable are established.
基金Supported by the National Natural Science Foundation of China(Grant No.11901268)the Ph.D Research Startup Foundation of Liaoning Normal University(Grant No.2021BSL011)。
文摘A traceable graph is a graph containing a Hamilton path.Let N[v]=N(v)∪{v}and J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.A graph G is cal_∑led quasi-claw-free if J(u,v)≠=?for any u,v∈V(G)with distance of two.Letσ_k(G)=min{∑_(v∈S)d(v):S is an independent set of V(G)with|S|=k},where d(v)denotes the degree of v in G.In this paper,we prove that if G is a connected quasi-claw-free graph of order n andσ_3(G)≥n-2,then G is traceable;moreover,we give an example to show the bound in our result is best possible.We obtain that if G is a connected quasi-claw-free graph of order n andσ_(2)(G)≥_(3)^(2(n-2)),then G is traceable.
