In a search for triangle-free graphs with arbitrarily large chromatic number,Mycielski developed a graph transformation that transforms a graph G into a new graph(G),which is called the Mycielskian of G.A generalisati...In a search for triangle-free graphs with arbitrarily large chromatic number,Mycielski developed a graph transformation that transforms a graph G into a new graph(G),which is called the Mycielskian of G.A generalisation of this transformation is the generalised Mycielskian,denoted bym(G),where m is a positive integer.This paper investigates the hamiltonicity and some matching-related properties of generalized Mycielskianm(G).展开更多
Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k...Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k+1, k≥2 ) claw-free graphs to provide a unified proof for G to be Hamiltonian, 1 -Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ k i=0N(Y i) and n(Y) in G for each independent set Y=｛y 0, y 1, …, y k｝ of the square graph of G , where b ( 0<b<k+1 ) is an integer, Y i=｛y i, y i-1, …, y i-(b-1)｝Y for i∈｛0, 1, …, k｝ , where subscriptions of y j s will be taken modulo k+1 , and n(Y)=｛v∈ V(G): dist (v, Y)≤ 2｝ .展开更多
Let G be a graph, an independent set Y in G is called an essential independent set (or essential set for simplicity), if there is {y 1,y 2} Y such that dist (y 1,y 2)=2. In this paper, we wi...Let G be a graph, an independent set Y in G is called an essential independent set (or essential set for simplicity), if there is {y 1,y 2} Y such that dist (y 1,y 2)=2. In this paper, we will use the technique of the vertex insertion on l connected ( l=k or k+1,k≥2 ) claw free graphs to provide a unified proof for G to be hamiltonian or 1 hamiltonian, the sufficient conditions are expressed by the inequality concerning ∑ki=0N(Y i) and n(Y) for each essential set Y={y 0,y 1,...,y k} of G , where Y i={y i,y i-1 ,...,y i-(b-1) }Y for i∈{0,1,...,k} (the subscriptions of y j ’s will be taken modulo k+1 ), b ( 0【b【k+1 ) is an integer, and n(Y)={v∈V(G): dist (v,Y)≤2 }.展开更多
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgra...Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.展开更多
Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an i...Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an independent set of G, |Y| = t}, It(G) = {Y|Y is an essential set of G, |Y| = t}. For ∈E It(G), let si(y) = |{v|v ∈V(G), |N(v) n Y| = i}|(i = 0, 1,…, t). Let X, Y g V(G). Define dist(X, Y) = dist(u, v), n(Y) = |{v|v ∈V(G), dist({v}, Y) ≤ 2}|. A non-negative rational sequence (a1，a2,…, ak+1) (k ≥2) is called an LTW-sequence, if it satisfies 1) a1 ≤ 1; 2) for arbitrary i1, i2,…，ih. ∈{2,3,……, k + 1}, The main new results of this paper are as follows: Let (a1， a2，… ak+1) be all LTW-sequence, and k ≥ 2. If G is a k-connected graph, and then G has a Hamilton cycle; if G is a (k + 1)-connected graph and for each then G is Hamilton-connected. The existing results are generalized by these since Ik+1(G) is replaced by I(G). We introduce a new technique of T-insertion in this paper， by using the T-vertex inserting lemmas we give a unified proof for a graph to be hamiltonian or Hamilton-connected.展开更多
BCube is one kind of important data center networks.Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks.So far,there have been many results concerning fault-tolerant Hami...BCube is one kind of important data center networks.Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks.So far,there have been many results concerning fault-tolerant Hamiltonicity and fault-tolerant Hamiltonian connectivity in some data center networks.However,these results only consider faulty edges and faulty servers.In this paper,we study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity of BCube(n,k)under considering faulty servers,faulty links/edges,and faulty switches.For any integers n≥2 and k≥0,let BCn,k be the logic structure of BCube(n,k)and F be the union of faulty elements of BCn,k,Let fv/fe,and fs be the number of faulty servers,faulty edges,and faulty switches of BCiLbe(n,k),respectively.We show that BCnik-F is fault-tolerant Hamiltonian if fv+fe+(n-1)/s≤(n-1)(k+1)-2 and BCn,k-F is fault-tolerant Hamiltonian-connected ifv,+fe+(n-1)fs≤(n-1)(k+1)-3.To the best of our knowledge,this paper is the first work which takes faulty switches into account to study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity in data center networks.展开更多
文摘In a search for triangle-free graphs with arbitrarily large chromatic number,Mycielski developed a graph transformation that transforms a graph G into a new graph(G),which is called the Mycielskian of G.A generalisation of this transformation is the generalised Mycielskian,denoted bym(G),where m is a positive integer.This paper investigates the hamiltonicity and some matching-related properties of generalized Mycielskianm(G).
文摘Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k+1, k≥2 ) claw-free graphs to provide a unified proof for G to be Hamiltonian, 1 -Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ k i=0N(Y i) and n(Y) in G for each independent set Y=｛y 0, y 1, …, y k｝ of the square graph of G , where b ( 0<b<k+1 ) is an integer, Y i=｛y i, y i-1, …, y i-(b-1)｝Y for i∈｛0, 1, …, k｝ , where subscriptions of y j s will be taken modulo k+1 , and n(Y)=｛v∈ V(G): dist (v, Y)≤ 2｝ .
文摘Let G be a graph, an independent set Y in G is called an essential independent set (or essential set for simplicity), if there is {y 1,y 2} Y such that dist (y 1,y 2)=2. In this paper, we will use the technique of the vertex insertion on l connected ( l=k or k+1,k≥2 ) claw free graphs to provide a unified proof for G to be hamiltonian or 1 hamiltonian, the sufficient conditions are expressed by the inequality concerning ∑ki=0N(Y i) and n(Y) for each essential set Y={y 0,y 1,...,y k} of G , where Y i={y i,y i-1 ,...,y i-(b-1) }Y for i∈{0,1,...,k} (the subscriptions of y j ’s will be taken modulo k+1 ), b ( 0【b【k+1 ) is an integer, and n(Y)={v∈V(G): dist (v,Y)≤2 }.
文摘Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.
文摘Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an independent set of G, |Y| = t}, It(G) = {Y|Y is an essential set of G, |Y| = t}. For ∈E It(G), let si(y) = |{v|v ∈V(G), |N(v) n Y| = i}|(i = 0, 1,…, t). Let X, Y g V(G). Define dist(X, Y) = dist(u, v), n(Y) = |{v|v ∈V(G), dist({v}, Y) ≤ 2}|. A non-negative rational sequence (a1，a2,…, ak+1) (k ≥2) is called an LTW-sequence, if it satisfies 1) a1 ≤ 1; 2) for arbitrary i1, i2,…，ih. ∈{2,3,……, k + 1}, The main new results of this paper are as follows: Let (a1， a2，… ak+1) be all LTW-sequence, and k ≥ 2. If G is a k-connected graph, and then G has a Hamilton cycle; if G is a (k + 1)-connected graph and for each then G is Hamilton-connected. The existing results are generalized by these since Ik+1(G) is replaced by I(G). We introduce a new technique of T-insertion in this paper， by using the T-vertex inserting lemmas we give a unified proof for a graph to be hamiltonian or Hamilton-connected.
基金supported by the National Natural Science Foundation of China under Grant Nos.U1905211,61572337,and 61972272Jiangsu Planned Projects for Postdoctoral Research Funds under Grant No.1701173B+1 种基金Application Foundation Research of Suzhou of China under Grant No.SYG201653a project funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.
文摘BCube is one kind of important data center networks.Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks.So far,there have been many results concerning fault-tolerant Hamiltonicity and fault-tolerant Hamiltonian connectivity in some data center networks.However,these results only consider faulty edges and faulty servers.In this paper,we study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity of BCube(n,k)under considering faulty servers,faulty links/edges,and faulty switches.For any integers n≥2 and k≥0,let BCn,k be the logic structure of BCube(n,k)and F be the union of faulty elements of BCn,k,Let fv/fe,and fs be the number of faulty servers,faulty edges,and faulty switches of BCiLbe(n,k),respectively.We show that BCnik-F is fault-tolerant Hamiltonian if fv+fe+(n-1)/s≤(n-1)(k+1)-2 and BCn,k-F is fault-tolerant Hamiltonian-connected ifv,+fe+(n-1)fs≤(n-1)(k+1)-3.To the best of our knowledge,this paper is the first work which takes faulty switches into account to study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity in data center networks.
