共查询到20条相似文献,搜索用时 125 毫秒
1.
2.
We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager (2012). Carragher, Choi, Delcourt, Erickson and West showed that for any -vertex graph there is a winning strategy for the cop on the graph obtained by replacing each edge of by a path of length , if (Carragher et al., 2012). The present authors showed that, for all but a few small values of , this bound may be improved to , which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of vertices, rather than a single vertex, at each turn. We consider the relationship between the value of required to ensure victory on the original graph with the length of subdivisions required to ensure victory with . We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree , which is best possible up to a factor of . 相似文献
3.
Very recently, Thomassé et al. (2017) have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time . In this article we improve this running time to . As a byproduct, we also improve the previous Turing-kernel for this problem from to . Furthermore, for the subclass of bull-free graphs without holes of length at most for , we speed up the running time to . As grows, this running time is asymptotically tight in terms of , since we prove that for each integer , Weighted Independent Set cannot be solved in time in the class of -free graphs unless the ETH fails. 相似文献
4.
The -power graph of a graph is a graph with the same vertex set as , in that two vertices are adjacent if and only if, there is a path between them in of length at most . A -tree-power graph is the -power graph of a tree, a -leaf-power graph is the subgraph of some -tree-power graph induced by the leaves of the tree.We show that (1) every -tree-power graph has NLC-width at most and clique-width at most , (2) every -leaf-power graph has NLC-width at most and clique-width at most , and (3) every -power graph of a graph of tree-width has NLC-width at most , and clique-width at most . 相似文献
5.
《Applied Mathematics Letters》2005,18(11):1286-1292
First a general model for two-step projection methods is introduced and second it has been applied to the approximation solvability of a system of nonlinear variational inequality problems in a Hilbert space setting. Let be a real Hilbert space and be a nonempty closed convex subset of . For arbitrarily chosen initial points , compute sequences and such that where is a nonlinear mapping on is the projection of onto , and . The two-step model is applied to some variational inequality problems. 相似文献
6.
7.
《Discrete Mathematics》2018,341(10):2708-2719
8.
9.
10.
11.
In Mader (2010), Mader conjectured that for every positive integer and every finite tree with order , every -connected, finite graph with contains a subtree isomorphic to such that is -connected. In the same paper, Mader proved that the conjecture is true when is a path. Diwan and Tholiya (2009) verified the conjecture when . In this paper, we will prove that Mader’s conjecture is true when is a star or double-star and . 相似文献
12.
The -restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset of a strong digraph is a -restricted arc cut if has a strong component with order at least such that contains a connected subdigraph with order at least . The -restricted arc connectivity of a digraph is the minimum cardinality over all -restricted arc cuts of .Let be a strong digraph with order and minimum degree . In this paper, we first show that exists if and, furthermore, if , where is the minimum 3-degree of . Next, we prove that if . Finally, we give examples showing that these results are best possible in some sense. 相似文献
13.
Let be the Galois ring of characteristic and cardinality . Firstly, we give all primitive idempotent generators of irreducible cyclic codes of length over , and a -adic integer ring with . Secondly, we obtain all primitive idempotents of all irreducible cyclic codes of length over , where and are three primes with , , and . Finally, as applications, weight distributions of all irreducible cyclic codes for and generator polynomials of self-dual cyclic codes of length and over are given. 相似文献
14.
15.
Jeong-Hyun Kang 《Discrete Mathematics》2018,341(1):96-103
The vertices of Kneser graph are the subsets of of cardinality , two vertices are adjacent if and only if they are disjoint. The square of a graph is defined on the vertex set of with two vertices adjacent if their distance in is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when . It is believed that where is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: for 1 (Kim and Park, 2014) and for (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to , where is a constant in , depending on . 相似文献
16.
Pierre Deligne 《Comptes Rendus Mathematique》2018,356(7):717-719
Let G be a reductive group over a field k of characteristic . For and , let be deduced from G by the extension of scalars . If k is perfect, this keeps making sense for . We show that, if k is perfect, there exists such that the algebraic groups G and over k are isomorphic. The isomorphism class of , as a reductive group over k, then depends only on n modulo m. For k not necessarily perfect, we show that such a periodicity remains true for n large enough. 相似文献
17.
18.
19.
Douglas P. Hardin Michael C. Northington Alexander M. Powell 《Applied and Computational Harmonic Analysis》2018,44(2):294-311
A sharp version of the Balian–Low theorem is proven for the generators of finitely generated shift-invariant spaces. If generators are translated along a lattice to form a frame or Riesz basis for a shift-invariant space V, and if V has extra invariance by a suitable finer lattice, then one of the generators must satisfy , namely, . Similar results are proven for frames of translates that are not Riesz bases without the assumption of extra lattice invariance. The best previously existing results in the literature give a notably weaker conclusion using the Sobolev space ; our results provide an absolutely sharp improvement with . Our results are sharp in the sense that cannot be replaced by for any . 相似文献
20.