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.展开更多
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.展开更多
For a graph G, we denote by p（G） and c（G） the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id（v） denotes the implicit degree of v. In this paper, we obtain th...For a graph G, we denote by p（G） and c（G） the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id（v） denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n ＋ 1, then either G contains a hamiltonian path, or c（G） 〉 p（G） - 1.展开更多
One method for identifying noncoding regulatory regions of a genome is to quantify rates of divergence between related species, as functional sequence will generally diverge more slowly. Most approaches to identifying...One method for identifying noncoding regulatory regions of a genome is to quantify rates of divergence between related species, as functional sequence will generally diverge more slowly. Most approaches to identifying these conserved noncoding sequences （CNSs） based on alignment have had relatively large minimum sequence lengths （≥15 bp） compared with the average length of known transcription factor binding sites. To circumvent this constraint, STAG-CNS that can simultaneously integrate the data from the promoters of conserved orthologous genes in three or more species was developed. Using the data from up to six grass species made it possible to identify conserved sequences as short as 9 bp with false discovery rate ≤0.05. These CNSs exhibit greater overlap with open chromatin regions identified using DNase I hypersensitivity assays, and are enriched in the promoters of genes involved in transcriptional regulation. STAG-CNS was further employed to characterize loss of conserved noncoding sequences associated with retained duplicate genes from the ancient maize polyploidy. Genes with fewer retained CNSs show lower overall expression, although this bias is more apparent in samples of complex organ systems containing many cell types, suggesting that CNS loss may correspond to a reduced number of expression contexts rather than lower expression levels across the entire ancestral expression domain.展开更多
文摘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.
基金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.
基金supported by the National Natural Science Foundation of China(Grant No.11501322)the Postdoctoral Science Foundation of China(Grant No.2015M571999)the Natural Science Foundation of Shandong Province(Grant No.ZR2014AP002)
文摘For a graph G, we denote by p（G） and c（G） the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id（v） denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n ＋ 1, then either G contains a hamiltonian path, or c（G） 〉 p（G） - 1.
文摘One method for identifying noncoding regulatory regions of a genome is to quantify rates of divergence between related species, as functional sequence will generally diverge more slowly. Most approaches to identifying these conserved noncoding sequences （CNSs） based on alignment have had relatively large minimum sequence lengths （≥15 bp） compared with the average length of known transcription factor binding sites. To circumvent this constraint, STAG-CNS that can simultaneously integrate the data from the promoters of conserved orthologous genes in three or more species was developed. Using the data from up to six grass species made it possible to identify conserved sequences as short as 9 bp with false discovery rate ≤0.05. These CNSs exhibit greater overlap with open chromatin regions identified using DNase I hypersensitivity assays, and are enriched in the promoters of genes involved in transcriptional regulation. STAG-CNS was further employed to characterize loss of conserved noncoding sequences associated with retained duplicate genes from the ancient maize polyploidy. Genes with fewer retained CNSs show lower overall expression, although this bias is more apparent in samples of complex organ systems containing many cell types, suggesting that CNS loss may correspond to a reduced number of expression contexts rather than lower expression levels across the entire ancestral expression domain.
