共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
A group-word w is called concise if whenever the set of w-values in a group G is finite it always follows that the verbal subgroup w(G) is finite. More generally, a word w is said to be concise in a class of groups X if whenever the set of w-values is finite for a group G∈X, it always follows that w(G) is finite. P. Hall asked whether every word is concise. Due to Ivanov the answer to this problem is known to be negative. Dan Segal asked whether every word is concise in the class of residually finite groups. In this direction we prove that if w is a multilinear commutator and q is a prime-power, then the word wq is indeed concise in the class of residually finite groups. Further, we show that in the case where w=γk the word wq is boundedly concise in the class of residually finite groups. It remains unknown whether the word wq is actually concise in the class of all groups. 相似文献
3.
In this paper, we derive mixture representations for the reliability function of the conditional residual lifetime of a coherent system with n independent and identically distributed (i.i.d.) components under the condition that at least j and at most k−1 (j<k) components have failed by time t. Based on these mixture representations, we then discuss stochastic comparisons of the conditional residual lifetimes of two coherent systems with independent and identical components. 相似文献
4.
It is shown that if a sequence of open n-sets Dk increases to an open n-set D then reflected stable processes in Dk converge weakly to the reflected stable process in D for every starting point x in D. The same result holds for censored α-stable processes for every x in D if D and Dk satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains. 相似文献
5.
6.
A polychromatic k-coloring of a map G on a surface is a k-coloring such that each face of G has all k colors on its boundary vertices. An even embedding G on a surface is a map of a simple graph on the surface such that each face of G is bounded by a cycle of even length. In this paper, we shall prove that a cubic even embedding G on the projective plane has a polychromatic proper 4-coloring if and only if G is not isomorphic to a Möbius ladder with an odd number of rungs. For proving the theorem, we establish a generating theorem for 3-connected Eulerian multi-triangulations on the projective plane. 相似文献
7.
The k-domination number of a graph is the minimum size of a set D such that every vertex of G is at distance at most k from D. We give a linear-time constant-factor algorithm for approximation of the k-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, proper classes closed on topological minors and classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge. 相似文献
8.
A semicomplete multipartite or semicomplete c-partite digraph D is a biorientation of a c-partite graph. A semicomplete multipartite digraph D is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x and y of D, there is a path P from x to y such that P contains at least one vertex from each partite set of D. 相似文献
9.
We give a combinatorial proof of the skew version of the K-saturation theorem. More precisely, for any positive integer k, we give an explicit injection from the set of skew semistandard Young tableaux with skew shape kλ/kμ and type kν, to the set of skew semistandard Young tableaux of shape λ/μ and type ν. 相似文献
10.
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). 相似文献
11.
Binh-Minh Bui-Xuan Ondřej Suchý Jan Arne Telle Martin Vatshelle 《European Journal of Combinatorics》2013
The Feedback Vertex Set problem asks whether a graph contains q vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if q vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph G of clique-width cw and a cw-expression of G, we solve the Minimum Feedback Vertex Set problem in time O(n22O(cwlogcw)). Our algorithm applies dynamic programming on a so-called k-module decomposition of a graph, as defined by Rao (2008) [29], which is easily derivable from ak-expression of the graph. The related notion of module-width of a graph is tightly linked to both clique-width and NLC-width, and in this paper we give an alternative equivalent characterization of module-width. 相似文献
12.
Maxime Crochemore Lucian Ilie Costas S. Iliopoulos Marcin Kubica Wojciech Rytter Tomasz Waleń 《European Journal of Combinatorics》2013
The Longest Previous Factor array gives, for each position i in a string y, the length of the longest factor (substring) of y that occurs both at i and to the left of i in y. The Longest Previous Factor array is central in many text compression techniques as well as in the most efficient algorithms for detecting motifs and repetitions occurring in a text. Computing the Longest Previous Factor array requires usually the Suffix Array and the Longest Common Prefix array. We give the first time–space optimal algorithm that computes the Longest Previous Factor array, given the Suffix Array and the Longest Common Prefix array. We also give the first linear-time algorithm that computes the permutation that applied to the Longest Common Prefix array produces the Longest Previous Factor array. 相似文献
13.
14.
Let T be a tree with s ends and f,g be continuous maps from T to T with f°g=g°f. In this note we show that if there exists a positive integer m≥2 such that gcd(m,l)=1 for any 2≤l≤s and f,g share a periodic point which is a km-periodic point of f for some positive integer k, then the topological entropy of f°g is positive. 相似文献
15.
Let G be a group. Any G-module M has an algebraic structure called a G-family of Alexander quandles. Given a 2-cocycle of a cohomology associated with this G-family, topological invariants of (handlebody) knots in the 3-sphere are defined. We develop a simple algorithm to algebraically construct n-cocycles of this G-family from G-invariant group n-cocycles of the abelian group M. We present many examples of 2-cocycles of these G-families using facts from (modular) invariant theory. 相似文献
17.
This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n vertices on each part and with costs on its edges, kMost Vital Edges Assignment consists of determining a set of k edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that kMost Vital Edges Assignment is NP-hard to approximate within a factor c<2 and Min Edge Blocker Assignment is NP-hard to approximate within a factor 1.36. We also provide an exact algorithm for kMost Vital Edges Assignment that runs in O(nk+2). This algorithm can also be used to solve exactly Min Edge Blocker Assignment. 相似文献
18.
We show that in a contest with a single prize, the expected effort made by the kth highest valuation participant bounds the sum of the expected efforts made by all of the participants with valuations less than the kth highest valuations. We also show that in the limit case of a contest with m prizes, the expected effort made by the kth highest valuation participant when the bidders are risk-neutral is greater than the expected effort in the risk-averse case. 相似文献
19.
Let E be a real Banach space, C be a nonempty closed convex subset of E and T:C→C be a continuous generalized Φ-pseudocontractive mapping. It is proved that T has a unique fixed point in C. 相似文献