共查询到20条相似文献,搜索用时 859 毫秒
1.
2.
3.
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. 相似文献
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.
A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G . We call these graphs γt-critical. If such a graph G has total domination number k, we call it k -γt-critical. We verify an open problem of k -γt-critical graphs and obtain some results on the characterization of total domination critical graphs of order n=Δ(G)(γt(G)-1)+1. 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
László Miklós Lovász Carsten Thomassen Yezhou Wu Cun-Quan Zhang 《Journal of Combinatorial Theory, Series B》2013
The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutte?s 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is Z3-connected, Jaeger?s circular flow conjecture (1984) that for every odd natural number k?3, every (2k−2)-edge-connected graph has a modulo k -orientation, etc. It was proved recently by Thomassen that, for every odd number k?3, every (2k2+k)-edge-connected graph G has a modulo k-orientation; and every 8-edge-connected graph G is Z3-connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassen?s method is refined to prove the following: For every odd number k?3, every (3k−3)-edge-connected graph has a modulo k-orientation. As a special case of the main result, every 6-edge-connected graph is Z3-connected and admits therefore a nowhere-zero 3-flow. Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs. 相似文献
9.
We prove that, unless assuming additional set theoretical axioms, there are no reflexive spaces without unconditional sequences of the density continuum. We show that for every integer n there are normalized weakly-null sequences of length ωn without unconditional subsequences. This together with a result of Dodos et al. (2011) [7] shows that ωω is the minimal cardinal κ that could possibly have the property that every weakly null κ-sequence has an infinite unconditional basic subsequence. We also prove that for every cardinal number κ which is smaller than the first ω-Erd?s cardinal there is a normalized weakly-null sequence without subsymmetric subsequences. Finally, we prove that mixed Tsirelson spaces of uncountable densities must always contain isomorphic copies of either c0 or ?p, with p≥1. 相似文献
10.
12.
13.
Let Gn,k denote the Kneser graph whose vertices are the n-element subsets of a (2n+k)-element set and whose edges are the disjoint pairs. In this paper we prove that for any non-negative integer s there is no graph homomorphism from G4,2 to G4s+1,2s+1. This confirms a conjecture of Stahl in a special case. 相似文献
14.
For s≥3 a graph is K1,s-free if it does not contain an induced subgraph isomorphic to K1,s. Cycles in K1,3-free graphs, called claw-free graphs, have been well studied. In this paper we extend results on disjoint cycles in claw-free graphs satisfying certain minimum degree conditions to K1,s-free graphs, normally called generalized claw-free graphs. In particular, we prove that if G is K1,s-free of sufficiently large order n=3k with δ(G)≥n/2+c for some constant c=c(s), then G contains k disjoint triangles. Analogous results with the complete graph K3 replaced by a complete graph Km for m≥3 will be proved. Also, the existence of 2-factors for K1,s-free graphs with minimum degree conditions will be shown. 相似文献
15.
16.
Let Qk denote the k-dimensional hypercube on 2k vertices. A vertex in a subgraph of Qk is full if its degree is k. We apply the Kruskal–Katona Theorem to compute the maximum number of full vertices an induced subgraph on n≤2k vertices of Qk can have, as a function of k and n. This is then used to determine min(max(|V(H1)|,|V(H2)|)) where (i) H1 and H2 are induced subgraphs of Qk, and (ii) together they cover all the edges of Qk, that is E(H1)∪E(H2)=E(Qk). 相似文献
17.
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. 相似文献
18.
Paul-Emile Maing 《Nonlinear Analysis: Theory, Methods & Applications》2008,68(12):3913-3922
This paper is concerned with the Cauchy problem for the fast diffusion equation ut−Δum=αup1 in RN (N≥1), where m∈(0,1), p1>1 and α>0. The initial condition u0 is assumed to be continuous, nonnegative and bounded. Using a technique of subsolutions, we set up sufficient conditions on the initial value u0 so that u(t,x) blows up in finite time, and we show how to get estimates on the profile of u(t,x) for small enough values of t>0. 相似文献
19.
We conjecture that the balanced complete bipartite graph K⌊n/2⌋,⌈n/2⌉ contains more cycles than any other n-vertex triangle-free graph, and we make some progress toward proving this. We give equivalent conditions for cycle-maximal triangle-free graphs; show bounds on the numbers of cycles in graphs depending on numbers of vertices and edges, girth, and homomorphisms to small fixed graphs; and use the bounds to show that among regular graphs, the conjecture holds. We also consider graphs that are close to being regular, with the minimum and maximum degrees differing by at most a positive integer k. For k=1, we show that any such counterexamples have n≤91 and are not homomorphic to C5; and for any fixed k there exists a finite upper bound on the number of vertices in a counterexample. Finally, we describe an algorithm for efficiently computing the matrix permanent (a #P-complete problem in general) in a special case used by our bounds. 相似文献
20.
Mehmet Özer Yasar Polatoglu Gürsel Hacibekiroglou Antonios Valaristos Amalia N. Miliou Antonios N. Anagnostopoulos Antanas Čenys 《Nonlinear Analysis: Theory, Methods & Applications》2008
The dynamic behaviour of the one-dimensional family of maps f(x)=c2[(a−1)x+c1]−λ/(α−1) is examined, for representative values of the control parameters a,c1, c2 and λ. The maps under consideration are of special interest, since they are solutions of the relaxed Newton method derivative being equal to a constant a. The maps f(x) are also proved to be solutions of a non-linear differential equation with outstanding applications in the field of power electronics. The recurrent form of these maps, after excessive iterations, shows, in an xn versus λ plot, an initial exponential decay followed by a bifurcation. The value of λ at which this bifurcation takes place depends on the values of the parameters a,c1 and c2. This corresponds to a switch to an oscillatory behaviour with amplitudes of f(x) undergoing a period doubling. For values of a higher than 1 and at higher values of λ a reverse bifurcation occurs. The corresponding branches converge and a bleb is formed for values of the parameter c1 between 1 and 1.20. This behaviour is confirmed by calculating the corresponding Lyapunov exponents. 相似文献