共查询到20条相似文献,搜索用时 78 毫秒
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.
Let k be any field, G be a finite group acting on the rational function field k(xg:g∈G) by h⋅xg=xhg for any h,g∈G. Define k(G)=k(xg:g∈G)G. Noether’s problem asks whether k(G) is rational (= purely transcendental) over k. A weaker notion, retract rationality introduced by Saltman, is also very useful for the study of Noether’s problem. We prove that, if G is a Frobenius group with abelian Frobenius kernel, then k(G) is retract k-rational for any field k satisfying some mild conditions. As an application, we show that, for any algebraic number field k, for any Frobenius group G with Frobenius complement isomorphic to SL2(F5), there is a Galois extension field K over k whose Galois group is isomorphic to G, i.e. the inverse Galois problem is valid for the pair (G,k). The same result is true for any non-solvable Frobenius group if k(ζ8) is a cyclic extension of k. 相似文献
3.
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. 相似文献
4.
Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d be an integer at least 3, and let G be a graph with maximum degree d. If G does not contain Kd+1 as a subgraph, then G has a d-coloring in which one color class has size α(G). Here α(G) denotes the independence number of G. We give a unified proof of Brooks’ theorem and Catlin’s theorem. 相似文献
5.
6.
7.
8.
Michel Mandjes Petteri Mannersalo Ilkka Norros Miranda van Uitert 《Stochastic Processes and their Applications》2006
Consider events of the form {Zs≥ζ(s),s∈S}, where Z is a continuous Gaussian process with stationary increments, ζ is a function that belongs to the reproducing kernel Hilbert space R of process Z, and S⊂R is compact. The main problem considered in this paper is identifying the function β∗∈R satisfying β∗(s)≥ζ(s) on S and having minimal R-norm. The smoothness (mean square differentiability) of Z turns out to have a crucial impact on the structure of the solution. As examples, we obtain the explicit solutions when ζ(s)=s for s∈[0,1] and Z is either a fractional Brownian motion or an integrated Ornstein–Uhlenbeck process. 相似文献
9.
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. 相似文献
10.
We consider G=Γ×S1 with Γ being a finite group, for which the complete Euler ring structure in U(G) is described. The multiplication tables for Γ=D6, S4 and A5 are provided in the Appendix. The equivariant degree for G-orthogonal maps is constructed using the primary equivariant degree with one free parameter. We show that the G-orthogonal degree extends the degree for G-gradient maps (in the case of G=Γ×S1) introduced by G?ba in [K. G?ba, W. Krawcewicz, J. Wu, An equivariant degree with applications to symmetric bifurcation problems I: Construction of the degree, Bull. London. Math. Soc. 69 (1994) 377–398]. The computational results obtained are applied to a Γ-symmetric autonomous Newtonian system for which we study the existence of 2π-periodic solutions. For some concrete cases, we present the symmetric classification of the solution set for the systems considered. 相似文献
11.
Let K be a closed convex subset of a q-uniformly smooth separable Banach space, T:K→K a strictly pseudocontractive mapping, and f:K→K an L-Lispschitzian strongly pseudocontractive mapping. For any t∈(0,1), let xt be the unique fixed point of tf+(1-t)T. We prove that if T has a fixed point, then {xt} converges to a fixed point of T as t approaches to 0. 相似文献
12.
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. 相似文献
13.
14.
We prove that if G is a finite simple group which is the unit group of a ring, then G is isomorphic to: (a) a cyclic group of order 2; or (b) a cyclic group of prime order 2k−1 for some k; or (c) a projective special linear group PSLn(F2) for some n≥3. Moreover, these groups do all occur as unit groups. We deduce this classification from a more general result, which holds for groups G with no non-trivial normal 2-subgroup. 相似文献
15.
Bosek and Krawczyk exhibited an on-line algorithm for partitioning an on-line poset of width w into w14lgw chains. They also observed that the problem of on-line chain partitioning of general posets of width w could be reduced to First-Fit chain partitioning of 2w2+1-ladder-free posets of width w, where an m-ladder is the transitive closure of the union of two incomparable chains x1≤?≤xm, y1≤?≤ym and the set of comparabilities {x1≤y1,…,xm≤ym}. Here, we provide a subexponential upper bound (in terms of w with m fixed) for the performance of First-Fit chain partitioning on m-ladder-free posets, as well as an exact quadratic bound when m=2, and an upper bound linear in m when w=2. Using the Bosek–Krawczyk observation, this yields an on-line chain partitioning algorithm with a somewhat improved performance bound. More importantly, the algorithm and the proof of its performance bound are much simpler. 相似文献
16.
In this paper we present an extension of the removal lemma to integer linear systems over abelian groups. We prove that, if the k-determinantal of an integer (k×m) matrix A is coprime with the order n of a group G and the number of solutions of the system Ax=b with x1∈X1,…,xm∈Xm is o(nm−k), then we can eliminate o(n) elements in each set to remove all these solutions. 相似文献
18.
Let R(G) be the graph obtained from G by adding a new vertex corresponding to each edge of G and by joining each new vertex to the end vertices of the corresponding edge, and Q(G) be the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we determine the Laplacian polynomials of R(G) and Q(G) of a regular graph G; on the other hand, we derive formulae and lower bounds of the Kirchhoff index of these graphs. 相似文献
20.
A subset S of vertices in a graph G=(V,E) is a connected dominating set of G if every vertex of V?S is adjacent to a vertex in S and the subgraph induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number γc(G). The girth g(G) is the length of a shortest cycle in G. We show that if G is a connected graph that contains at least one cycle, then γc(G)≥g(G)−2, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results. 相似文献