In this paper,we consider Seymour’s Second Neighborhood Conjecture in3-free digraphs,and prove that for any 3-free digraph D,there exists a vertex say v,such that d^++(v)≥[λd+(v)],λ=0.6958….This slightly improves...In this paper,we consider Seymour’s Second Neighborhood Conjecture in3-free digraphs,and prove that for any 3-free digraph D,there exists a vertex say v,such that d^++(v)≥[λd+(v)],λ=0.6958….This slightly improves the known results in 3-free digraphs with large minimum out-degree.展开更多
Based on the range space property （RSP）, the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted l1-norm minimization problem are studied in this paper. Different...Based on the range space property （RSP）, the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted l1-norm minimization problem are studied in this paper. Different from other conditions based on the spark property, the mutual coherence, the null space property （NSP） and the restricted isometry property （RIP）, the RSP- based conditions are easier to be verified. Moreover, the proposed conditions guarantee not only the strong equivalence, but also the equivalence between the two problems. First, according to the foundation of the strict complemenrarity theorem of linear programming, a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix, is presented for the unique nonnegative solution to the weighted l1-norm minimization problem. Then, based on this condition, the equivalence conditions between the two problems are proposed. Finally, this paper shows that the matrix with the RSP of order k can guarantee the strong equivalence of the two problems.展开更多
A graph G is k-triangular if each of its edge is contained in at least k triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph G is a sequen...A graph G is k-triangular if each of its edge is contained in at least k triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph G is a sequence of distinct triangles T1T2%…Tk in G such that for 1 〈 i 〈 k - 1, IE（Ti）∩E（Ti＋1）1= 1 and E（Ti） n E（Tj）=φ if j 〉 i＋1. Two edges e, e＇∈ E（G） are triangularly connected if there is a triangle-path T1, T2,... , Tk in G such that e ∈ E（T1） and er ∈ E（Tk）. Two edges e, e＇ ∈E（G） are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph G is Z3-connected, unless it has a triangularly connected component which is not Z3-connected but admits a nowhere-zero 3-flow.展开更多
文摘In this paper,we consider Seymour’s Second Neighborhood Conjecture in3-free digraphs,and prove that for any 3-free digraph D,there exists a vertex say v,such that d^++(v)≥[λd+(v)],λ=0.6958….This slightly improves the known results in 3-free digraphs with large minimum out-degree.
基金Research supported by the National Natural Science Foundation of China under Grant 61672005
文摘Based on the range space property （RSP）, the equivalent conditions between nonnegative solutions to the partial sparse and the corresponding weighted l1-norm minimization problem are studied in this paper. Different from other conditions based on the spark property, the mutual coherence, the null space property （NSP） and the restricted isometry property （RIP）, the RSP- based conditions are easier to be verified. Moreover, the proposed conditions guarantee not only the strong equivalence, but also the equivalence between the two problems. First, according to the foundation of the strict complemenrarity theorem of linear programming, a sufficient and necessary condition, satisfying the RSP of the sensing matrix and the full column rank property of the corresponding sub-matrix, is presented for the unique nonnegative solution to the weighted l1-norm minimization problem. Then, based on this condition, the equivalence conditions between the two problems are proposed. Finally, this paper shows that the matrix with the RSP of order k can guarantee the strong equivalence of the two problems.
文摘A graph G is k-triangular if each of its edge is contained in at least k triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph G is a sequence of distinct triangles T1T2%…Tk in G such that for 1 〈 i 〈 k - 1, IE（Ti）∩E（Ti＋1）1= 1 and E（Ti） n E（Tj）=φ if j 〉 i＋1. Two edges e, e＇∈ E（G） are triangularly connected if there is a triangle-path T1, T2,... , Tk in G such that e ∈ E（T1） and er ∈ E（Tk）. Two edges e, e＇ ∈E（G） are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph G is Z3-connected, unless it has a triangularly connected component which is not Z3-connected but admits a nowhere-zero 3-flow.
