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.展开更多
Based on the ideas in[9],an integer d<sup>0</sup>（v）,called the implicit degree of v whichsatisfies d<sup>0</sup>（v）≥d（v）,is associated with each vertex v of a graph G.It is proved that ...Based on the ideas in[9],an integer d<sup>0</sup>（v）,called the implicit degree of v whichsatisfies d<sup>0</sup>（v）≥d（v）,is associated with each vertex v of a graph G.It is proved that if theimplicit degree sequence d<sub>1</sub><sup>0</sup>,d<sub>2</sub><sup>0</sup>,…,d<sub>n</sub><sup>0</sup>（where d<sub>1</sub><sup>0</sup>≤d<sub>2</sub><sup>0</sup>≤…≤d<sub>n</sub><sup>0</sup>）of a simple graph G on n≥3vertices satisfiesd<sub>i</sub><sup>0</sup>≤i【n/2（?）d<sub>n-i</sub><sup>0</sup>≥n-i,then G is hamiltonian.This is an improvement of the well-known theorem of Chvatal（[4]）.展开更多
A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show t...A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show that if G is.3-connected claw-free graph and(1)if for each vertex V the set of venices at distance three from v doesn’tcontain and independent subset of size three,then G is hamiltonian;(2) if G contains no induced subgraph with degree sequence(1,1,1,2,2,2,3,3,3),so that ear vertel of degree is adjacent to a vertex of degree i + 1 for i=1,2,then G is hamiltonoan. Furthermore,we obtain a generalization of both(1) and(2),in which the graphs F1 and F2coatain an the known forbidded subgraphs given in[3] as indeced subgraphs.展开更多
In this note, we denote by G a graph with order n, by V and E the vertex set andedge set of G, respectively. V<sub>0</sub>={v∈V|d（v）≥n/2}, V<sub>0</sub>=V\V<sub>0</sub>. Let H b...In this note, we denote by G a graph with order n, by V and E the vertex set andedge set of G, respectively. V<sub>0</sub>={v∈V|d（v）≥n/2}, V<sub>0</sub>=V\V<sub>0</sub>. Let H be a subgraph ofG. For simplicity, we also use H to denote the vertex set of it. For a∈V S, TV,展开更多
Let F be a graph consisting of a triangle with a pendant leaf dangling from each vertex.A graph is{K_(1,3),F}-free if it contains no induced subgraph isomorphic to K_(1,3)or F.We give a stronger structural characteris...Let F be a graph consisting of a triangle with a pendant leaf dangling from each vertex.A graph is{K_(1,3),F}-free if it contains no induced subgraph isomorphic to K_(1,3)or F.We give a stronger structural characterisation of{K_(1,3),F}-free graph with which we obtain a more general result than that in[1]as follows:Given any two venices in a 2-connected{K_(1,3),F}-free graph,if there exists a shortest path between them containing no 2-cutset of the graph,then the graph has a Hamilton path cormecting these two venices.展开更多
文摘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.
文摘Based on the ideas in[9],an integer d<sup>0</sup>（v）,called the implicit degree of v whichsatisfies d<sup>0</sup>（v）≥d（v）,is associated with each vertex v of a graph G.It is proved that if theimplicit degree sequence d<sub>1</sub><sup>0</sup>,d<sub>2</sub><sup>0</sup>,…,d<sub>n</sub><sup>0</sup>（where d<sub>1</sub><sup>0</sup>≤d<sub>2</sub><sup>0</sup>≤…≤d<sub>n</sub><sup>0</sup>）of a simple graph G on n≥3vertices satisfiesd<sub>i</sub><sup>0</sup>≤i【n/2（?）d<sub>n-i</sub><sup>0</sup>≥n-i,then G is hamiltonian.This is an improvement of the well-known theorem of Chvatal（[4]）.
文摘A graph is claw-free if it contains no induced subgraph isomorphic to a K1,3.This paper studies hamiltonicity in 3-connected claw-free graphs.Four generation of Shepherd’s result[4] are obtained.For example,we show that if G is.3-connected claw-free graph and(1)if for each vertex V the set of venices at distance three from v doesn’tcontain and independent subset of size three,then G is hamiltonian;(2) if G contains no induced subgraph with degree sequence(1,1,1,2,2,2,3,3,3),so that ear vertel of degree is adjacent to a vertex of degree i + 1 for i=1,2,then G is hamiltonoan. Furthermore,we obtain a generalization of both(1) and(2),in which the graphs F1 and F2coatain an the known forbidded subgraphs given in[3] as indeced subgraphs.
文摘In this note, we denote by G a graph with order n, by V and E the vertex set andedge set of G, respectively. V<sub>0</sub>={v∈V|d（v）≥n/2}, V<sub>0</sub>=V\V<sub>0</sub>. Let H be a subgraph ofG. For simplicity, we also use H to denote the vertex set of it. For a∈V S, TV,
基金This research is supported by the National Natural Science Foundation of China.
文摘Let F be a graph consisting of a triangle with a pendant leaf dangling from each vertex.A graph is{K_(1,3),F}-free if it contains no induced subgraph isomorphic to K_(1,3)or F.We give a stronger structural characterisation of{K_(1,3),F}-free graph with which we obtain a more general result than that in[1]as follows:Given any two venices in a 2-connected{K_(1,3),F}-free graph,if there exists a shortest path between them containing no 2-cutset of the graph,then the graph has a Hamilton path cormecting these two venices.
