共查询到20条相似文献,搜索用时 15 毫秒
1.
Daniela Ferrero Leslie Hogben Franklin H.J. Kenter Michael Young 《Discrete Mathematics》2018,341(6):1789-1797
Zero forcing and power domination are iterative processes on graphs where an initial set of vertices are observed, and additional vertices become observed based on some rules. In both cases, the goal is to eventually observe the entire graph using the fewest number of initial vertices. The concept of -power domination was introduced by Chang et al. (2012) as a generalization of power domination and standard graph domination. Independently, -forcing was defined by Amos et al. (2015) to generalize zero forcing. In this paper, we combine the study of -forcing and -power domination, providing a new approach to analyze both processes. We give a relationship between the -forcing and the -power domination numbers of a graph that bounds one in terms of the other. We also obtain results using the contraction of subgraphs that allow the parallel computation of -forcing and -power dominating sets. 相似文献
2.
3.
Houssein El Turkey 《Journal of Pure and Applied Algebra》2018,222(1):181-190
The complexity of a module is the rate of growth of the minimal projective resolution of the module while the z-complexity is the rate of growth of the number of indecomposable summands at each step in the resolution. Let () be the type II orthosymplectic Lie superalgebra of types B or D. In this paper, we compute the complexity and the z-complexity of the simple finite-dimensional -supermodules. We then give these complexities certain geometric interpretations using support and associated varieties. 相似文献
4.
Tutte’s -flow conjecture states that every -edge-connected graph admits a nowhere-zero -flow. In this paper, we characterize all graphs with independence number at most that admit a nowhere-zero -flow. The characterization of -flow verifies Tutte’s -flow conjecture for graphs with independence number at most and with order at least . In addition, we prove that every odd--edge-connected graph with independence number at most admits a nowhere-zero -flow. To obtain these results, we introduce a new reduction method to handle odd wheels. 相似文献
5.
Aysel Erey 《Discrete Mathematics》2018,341(5):1419-1431
6.
In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph . We showed that the is 3-spanning connected for odd . Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the . In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for , where a lattice tail is a trail in the lattice model that represents a path in . 相似文献
7.
Alexey Ananyevskiy 《Journal of Pure and Applied Algebra》2018,222(10):3195-3218
We provide a cohomological interpretation of the zeroth stable -homotopy group of a smooth curve over an infinite perfect field. We show that this group is isomorphic to the first Nisnevich (or Zariski) cohomology group of a certain sheaf closely related to the first Milnor–Witt K-theory sheaf. This cohomology group can be computed using an explicit Gersten-type complex. We show that if the base field is algebraically closed then the zeroth stable -homotopy group of a smooth curve coincides with the zeroth Suslin homology group that was identified by Suslin and Voevodsky with a relative Picard group. As a consequence we reobtain a version of Suslin's rigidity theorem. 相似文献
8.
Let be a prime power and be a positive integer. A subspace partition of , the vector space of dimension over , is a collection of subspaces of such that each nonzero vector of is contained in exactly one subspace in ; the multiset of dimensions of subspaces in is then called a Gaussian partition of . We say that contains a direct sum if there exist subspaces such that . In this paper, we study the problem of classifying the subspace partitions that contain a direct sum. In particular, given integers and with , our main theorem shows that if is a subspace partition of with subspaces of dimension for , then contains a direct sum when has a solution for some integers and belongs to the union of two natural intervals. The lower bound of captures all subspace partitions with dimensions in that are currently known to exist. Moreover, we show the existence of infinite classes of subspace partitions without a direct sum when or when the condition on the existence of a nonnegative integral solution is not satisfied. We further conjecture that this theorem can be extended to any number of distinct dimensions, where the number of subspaces in each dimension has appropriate bounds. These results offer further evidence of the natural combinatorial relationship between Gaussian and integer partitions (when ) as well as subspace and set partitions. 相似文献
9.
10.
The graph grabbing game is a two-player game on weighted connected graphs where all weights are non-negative. Two players, Alice and Bob, alternately remove a non-cut vertex from the graph (i.e., the resulting graph is still connected) and get the weight assigned to the vertex, where the starting player is Alice. Each player’s aim is to maximize his/her outcome when all vertices have been taken, and Alice wins the game if she gathered at least half of the total weight. Seacrest and Seacrest (2017) proved that Alice has a winning strategy for every weighted tree with even order, and conjectured that the same statement holds for every weighted connected bipartite graph with even order. In this paper, we prove that Alice wins the game on a type of a connected bipartite graph with even order called a -tree. 相似文献
11.
12.
Ju Zhou 《Discrete Mathematics》2018,341(4):1021-1031
A graph is induced matching extendable or IM-extendable if every induced matching of is contained in a perfect matching of . In 1998, Yuan proved that a connected IM-extendable graph on vertices has at least edges, and that the only IM-extendable graph with vertices and edges is , where is an arbitrary tree on vertices. In 2005, Zhou and Yuan proved that the only IM-extendable graph with vertices and edges is , where is an arbitrary tree on vertices and is an edge connecting two vertices that lie in different copies of and have distance 3 between them in . In this paper, we introduced the definition of -joint graph and characterized the connected IM-extendable graphs with vertices and edges. 相似文献
13.
The purpose of this paper is to characterize and interrelate various degrees of stability and semipositivity for real square matrices having nonpositive off-diagonal entries. The major classes considered are the sets of diagonally stable, stable, and semipositive matrices, denoted respectively by , , and . The conditions defining these classes are weakened, and the resulting classes are examined. Their relationship to the classes of real matrices and 0, whose off-diagonal entries are nonpositive and whose principal minors are respectively all positive and all nonnegative, is also included. 相似文献
14.
David Gilat Isaac Meilijson Laura Sacerdote 《Stochastic Processes and their Applications》2018,128(6):1849-1856
For a martingale starting at with final variance , and an interval , let be the normalized length of the interval and let be the normalized distance from the initial point to the lower endpoint of the interval. The expected number of upcrossings of by is at most if and at most otherwise. Both bounds are sharp, attained by Standard Brownian Motion stopped at appropriate stopping times. Both bounds also attain the Doob upper bound on the expected number of upcrossings of for submartingales with the corresponding final distribution. Each of these two bounds is at most , with equality in the first bound for . The upper bound on the length covered by during upcrossings of an interval restricts the possible variability of a martingale in terms of its final variance. This is in the same spirit as the Dubins & Schwarz sharp upper bound on the expected maximum of above , the Dubins & Schwarz sharp upper bound on the expected maximal distance of from , and the Dubins, Gilat & Meilijson sharp upper bound on the expected diameter of . 相似文献
15.
Pasha Zusmanovich 《Indagationes Mathematicae》2019,30(2):288-299
We prove that a Lie -algebra of cohomological dimension one is one-dimensional, and discuss related questions. 相似文献
16.
A graph is minimally -tough if the toughness of is and the deletion of any edge from decreases the toughness. Kriesell conjectured that for every minimally -tough graph the minimum degree . We show that in every minimally -tough graph . We also prove that every minimally -tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number any graph can be embedded as an induced subgraph into a minimally -tough graph. 相似文献
17.
A second order asymptotic expansion in the local limit theorem for a simple branching random walk in
Zhi-Qiang Gao 《Stochastic Processes and their Applications》2018,128(12):4000-4017
Consider a branching random walk, where the underlying branching mechanism is governed by a Galton–Watson process and the migration of particles by a simple random walk in . Denote by the number of particles of generation located at site . We give the second order asymptotic expansion for . The higher order expansion can be derived by using our method here. As a by-product, we give the second order expansion for a simple random walk on , which is used in the proof of the main theorem and is of independent interest. 相似文献
18.
Given a nonnegative integer and a positive integer , a graph is said to be -colorable if the vertices of can be colored with colors such that every vertex has at most neighbors receiving the same color as itself. Let be the family of planar graphs without -cycles adjacent to cycles of length 3 or 5. This paper proves that everyone in is -colorable. This is the best possible in the sense that there are members in which are not -colorable. 相似文献
19.
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 . 相似文献
20.
The purpose of this note is to show a new series of examples of homogeneous ideals I in for which the containment fails. These ideals are supported on certain arrangements of lines in , which resemble Fermat configurations of points in , see [14]. All examples exhibiting the failure of the containment constructed so far have been supported on points or cones over configurations of points. Apart from providing new counterexamples, these ideals seem quite interesting on their own. 相似文献