共查询到20条相似文献,搜索用时 15 毫秒
1.
Consider a graph G with a minimal edge cut F and let G1, G2 be the two (augmented) components of G−F. A long-open question asks under which conditions the crossing number of G is (greater than or) equal to the sum of the crossing numbers of G1 and G2—which would allow us to consider those graphs separately. It is known that crossing number is additive for |F|∈{0,1,2} and that there exist graphs violating this property with |F|≥4. In this paper, we show that crossing number is additive for |F|=3, thus closing the final gap in the question. 相似文献
2.
Mustapha Chellali Teresa W. Haynes Stephen T. Hedetniemi Alice McRae 《Discrete Applied Mathematics》2013
A subset S⊆V in a graph G=(V,E) is a [j,k]-set if, for every vertex v∈V?S, j≤|N(v)∩S|≤k for non-negative integers j and k, that is, every vertex v∈V?S is adjacent to at least j but not more than k vertices in S. In this paper, we focus on small j and k, and relate the concept of [j,k]-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G, the restrained domination number is equal to the domination number of G. 相似文献
4.
5.
Let FFv be the set of faulty nodes in an n-dimensional folded hypercube FQn with |FFv|≤n−2. In this paper, we show that if n≥3, then every edge of FQn−FFv lies on a fault-free cycle of every even length from 4 to 2n−2|FFv|, and if n≥2 and n is even, then every edge of FQn−FFv lies on a fault-free cycle of every odd length from n+1 to 2n−2|FFv|−1. 相似文献
6.
Kelly, Kühn and Osthus conjectured that for any ?≥4 and the smallest number k≥3 that does not divide ?, any large enough oriented graph G with δ+(G),δ−(G)≥⌊|V(G)|/k⌋+1 contains a directed cycle of length ?. We prove this conjecture asymptotically for the case when ? is large enough compared to k and k≥7. The case when k≤6 was already settled asymptotically by Kelly, Kühn and Osthus. 相似文献
7.
A finite Sturmian word w is a balanced word over the binary alphabet {a,b}, that is, for all subwords u and v of w of equal length, ||u|a−|v|a|≤1, where |u|a and |v|a denote the number of occurrences of the letter a in u and v, respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity. 相似文献
8.
In 1994 Dias da Silva and Hamidoune solved a long-standing open problem of Erd?s and Heilbronn using the structure of cyclic spaces for derivatives on Grassmannians and the representation theory of symmetric groups. They proved that for any subset A of the p-element group Z/pZ (where p is a prime), at least min{p,m|A|−m2+1} different elements of the group can be written as the sum of m different elements of A. In this note we present an easily accessible simplified version of their proof for the case m=2, and explain how the method can be applied to obtain the corresponding inverse theorem. 相似文献
9.
The sum–product conjecture of Erd?s and Szemerédi states that, given a finite set A of positive numbers, one can find asymptotic lower bounds for max{|A+A|,|A⋅A|} of the order of |A|1+δ for every δ<1. In this paper we consider the set of all spectral radii of n×n matrices with entries in A, and find lower bounds for the cardinality of this set. In the case n=2, this cardinality is necessarily larger than max{|A+A|,|A⋅A|}. 相似文献
10.
Let us fix a function f(n)=o(nlnn) and real numbers 0≤α<β≤1. We present a polynomial time algorithm which, given a directed graph G with n vertices, decides either that one can add at most βn new edges to G so that G acquires a Hamiltonian circuit or that one cannot add αn or fewer new edges to G so that G acquires at least e−f(n)n! Hamiltonian circuits, or both. 相似文献
11.
In many applications it has been observed that hybrid-Monte Carlo sequences perform better than Monte Carlo and quasi-Monte Carlo sequences, especially in difficult problems. For a mixed s-dimensional sequence m, whose elements are vectors obtained by concatenating d-dimensional vectors from a low-discrepancy sequence q with (s−d)-dimensional random vectors, probabilistic upper bounds for its star discrepancy have been provided. In a paper of G. Ökten, B. Tuffin and V. Burago [G. Ökten, B. Tuffin, V. Burago, J. Complexity 22 (2006), 435–458] it was shown that for arbitrary ε>0 the difference of the star discrepancies of the first N points of m and q is bounded by ε with probability at least 1−2exp(−ε2N/2) for N sufficiently large. The authors did not study how large N actually has to be and if and how this actually depends on the parameters s and ε. In this note we derive a lower bound for N, which significantly depends on s and ε. Furthermore, we provide a probabilistic bound for the difference of the star discrepancies of the first N points of m and q, which holds without any restrictions on N. In this sense it improves on the bound of Ökten, Tuffin and Burago and is more helpful in practice, especially for small sample sizes N. We compare this bound to other known bounds. 相似文献
12.
Let X be a finite graph. Let |V| be the number of its vertices and d be its degree. Denote by F1(X) its first spectral density function which counts the number of eigenvalues ≤λ2 of the associated Laplace operator. We provide an elementary proof for the estimate F1(X)(λ)−F1(X)(0)≤2⋅(|V|−1)⋅d⋅λ for 0≤λ<1 which has already been proved by Friedman (1996) [3] before. We explain how this gives evidence for conjectures about approximating Fuglede–Kadison determinants and L2-torsion. 相似文献
13.
14.
16.
Angela Alberico Teresa Alberico Carlo Sbordone 《Nonlinear Analysis: Theory, Methods & Applications》2012
We give a Sobolev inequality with the weight K(x) belonging to the class A2∩Gn for the function |u|t and the weight K(x)−1 for |∇u|2. The constant in the relevant inequality is seen to depend on the Gn and A2 constants of the weight. 相似文献
17.
Let R be a commutative ring with identity. We will say that an R-module M satisfies the weak Nakayama property, if IM=M, where I is an ideal of R, implies that for any x∈M there exists a∈I such that (a−1)x=0. In this paper, we will study modules satisfying the weak Nakayama property. It is proved that if R is a local ring, then R is a Max ring if and only if J(R), the Jacobson radical of R, is T-nilpotent if and only if every R-module satisfies the weak Nakayama property. 相似文献
18.
19.
In 2011, the fundamental gap conjecture for Schrödinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schrödinger equation with a convex potential and relative error ε. Classical deterministic algorithms solving this problem have cost exponential in the number of its degrees of freedom d. We show a quantum algorithm, that is based on a perturbation method, for estimating the ground state energy with relative error ε. The cost of the algorithm is polynomial in d and ε−1, while the number of qubits is polynomial in d and logε−1. In addition, we present an algorithm for preparing a quantum state that overlaps within 1−δ,δ∈(0,1), with the ground state eigenvector of the discretized Hamiltonian. This algorithm also approximates the ground state with relative error ε. The cost of the algorithm is polynomial in d, ε−1 and δ−1, while the number of qubits is polynomial in d, logε−1 and logδ−1. 相似文献
20.
In this note we study distance-regular graphs with a small number of vertices compared to the valency. We show that for a given α>2, there are finitely many distance-regular graphs Γ with valency k, diameter D≥3 and v vertices satisfying v≤αk unless (D=3 and Γ is imprimitive) or (D=4 and Γ is antipodal and bipartite). We also show, as a consequence of this result, that there are finitely many distance-regular graphs with valency k≥3, diameter D≥3 and c2≥εk for a given 0<ε<1 unless (D=3 and Γ is imprimitive) or (D=4 and Γ is antipodal and bipartite). 相似文献