A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two d...A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.展开更多
We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the lo...We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.展开更多
A graph G is{K_(1,4),K_(1,4)+e}-free if G contains no induced subgraph isomorphic to K_(1,4) or KI,a+e In this paper,we show that G has a path which is either hamiltonian or of length at least 25(G)+2 if G is a connec...A graph G is{K_(1,4),K_(1,4)+e}-free if G contains no induced subgraph isomorphic to K_(1,4) or KI,a+e In this paper,we show that G has a path which is either hamiltonian or of length at least 25(G)+2 if G is a connected{K_(1,4),K_(1,4)+e}-free graph on at least 7 vertices.展开更多
文摘A graph is called claw-free if it does not contain a claw as its induced subgraph.In this paper, we prove the following results:1)If G is a 2-connected claw-free graph on n vertices,then for any vertex v and any two distinct vertices x and y in V(G)-{v},G has a path containing v and all neighbors of v and connecting x and y;2) Let C be the longest cycle in a 3-connected claw-free graph G and H a component of G-C,and if H is connected but not 2-connected,then there exist nonadjacent vertices u and v in H such that |V(C)|≥(3(d(u)+)d(v))-2.
文摘We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.
基金Supported by Scientific Research Program of the Higher Education Institution of Xinjiang(Grant No.2011S30)Science Foundation of Xinjiang Normal University
文摘A graph G is{K_(1,4),K_(1,4)+e}-free if G contains no induced subgraph isomorphic to K_(1,4) or KI,a+e In this paper,we show that G has a path which is either hamiltonian or of length at least 25(G)+2 if G is a connected{K_(1,4),K_(1,4)+e}-free graph on at least 7 vertices.
