共查询到20条相似文献,搜索用时 687 毫秒
1.
In this paper, by using the Discharging Method, we show that any graph with maximum degree Δ 8 that is embeddable in a surface Σ of characteristic χ(Σ) 0 is class one and any graph with maximum degree Δ 9 that is embeddable in a surface Σ of characteristic χ(Σ) = − 1 is class one. For surfaces of characteristic 0 or −1, these results improve earlier results of Mel'nikov. 相似文献
2.
In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}. 相似文献
3.
It was conjectured by Reed [B. Reed, ω,α, and χ, Journal of Graph Theory 27 (1998) 177–212] that for any graph G, the graph’s chromatic number χ(G) is bounded above by , where Δ(G) and ω(G) are the maximum degree and clique number of G, respectively. In this paper we prove that this bound holds if G is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph G and produces a colouring that achieves our bound. 相似文献
4.
Peter Bella Daniel Krl Bojan Mohar Katarína Quittnerov 《European Journal of Combinatorics》2007,28(8):2201
An L(2,1)-labeling of a graph is a mapping c:V(G)→{0,…,K} such that the labels assigned to neighboring vertices differ by at least 2 and the labels of vertices at distance two are different. The smallest K for which an L(2,1)-labeling of a graph G exists is denoted by λ2,1(G). Griggs and Yeh [J.R. Griggs, R.K. Yeh, Labeling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595] conjectured that λ2,1(G)≤Δ2 for every graph G with maximum degree Δ≥2. We prove the conjecture for planar graphs with maximum degree Δ≠3. All our results also generalize to the list-coloring setting. 相似文献
5.
Dimitris A. Fotakis Sotiris E. Nikoletseas Vicky G. Papadopoulou Paul G. Spirakis 《Journal of Discrete Algorithms》2006,4(3):433
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Λ(u)−Λ(v)|2, when u,v are neighbors in G, and |Λ(u)−Λ(v)|1 when the distance of u,v in G is two. The discrete number of frequencies used is called order and the range of frequencies used, span. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span (min span RCP) or the order (min order RCP).In this paper, we deal with an interesting, yet not examined until now, variation of the radiocoloring problem: that of satisfying frequency assignment requests which exhibit some periodic behavior. In this case, the interference graph (modelling interference between transmitters) is some (infinite) periodic graph. Infinite periodic graphs usually model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they can model very large networks produced by the repetition of a small graph.A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph Gi(Vi,Ei). The edge set of G is derived by connecting the vertices of each iteration Gi to some of the vertices of the next iteration Gi+1, the same for all Gi. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest.We give two basic results:
- • We prove that the min span RCP is PSPACE-complete for periodic planar graphs.
- • We provide an O(n(Δ(Gi)+σ)) time algorithm (where|Vi|=n, Δ(Gi) is the maximum degree of the graph Gi and σ is the number of edges connecting each Gi to Gi+1), which obtains a radiocoloring of a periodic planar graph G that approximates the minimum span within a ratio which tends to as Δ(Gi)+σ tends to infinity.
Keywords: Approximation algorithms; Computational complexity; Radio networks; Frequency assignment; Coloring; Periodic graphs 相似文献
6.
We compare the degree of approximation to L2(−π, π) by nth degree trigonometric polynomials, with the degree of approximation by trigonometric n-nomials, which are linear combinations, with constant (complex) coefficients, of any 2n + 1 members of the sequence {exp (ikx)}, − ∞ < k < ∞. 相似文献
7.
The energy E(G) of a graph G is defined as the sum of the absolute values of its eigenvalues. A connected graph G of order n is said to be hypoenergetic if E(G)<n. All connected hypoenergetic graphs with maximum degree Δ3 have been characterized. In addition to the four (earlier known) hypoenergetic trees, we now show that complete bipartite graph K2,3 is the only hypoenergetic cycle-containing hypoenergetic graph. By this, the validity of a conjecture by Majstorović et al. has been confirmed. 相似文献
8.
A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C5 and Δ(G)≥3, then , where Δ(G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ2(G)≤Δ(G)+1. Among other results, we determine , for every natural number n. 相似文献
9.
We investigate the large-time behaviour of solutions to the nonlinear heat-conduction equation with absorption ut = Δ(uσ + 1) − uβ in Q = RN × (0, ∞) (E) with N 1, σ > 0 and critical absorption exponent β = σ + 1 + 2/N; the initial function u(x, 0) = 0 is assumed to be integrable, nonnegative and compactly supported. We prove that u converges as t → ∞ to a unique self-similar function which is a contracted version of one of the asymptotic profiles of the nonabsorptive problem ut = Δ(uσ + 1), the same for any initial data. The cornerstone of the proof is a result about ω-limits of (infinite-dimensional) asymptotical dynamical systems. Combining this result with an asymptotic evaluation of the mass function as well as typical PDE estimates gives the behaviour of (E) for large times.Similar unusual asymptotic behaviour is obtained for the equation ut = div(¦Du¦σ Du) − uβ with same conditions on σ and u(x, 0) and critical value for β = σ + 1 + (σ + 2)/N. 相似文献
10.
Let r1 > r2 > … be the sample canonical correlations in a sample of size n from a multivariate normal population partitioned into two subvectors with population canonical correlations 1 > 2 > …. Let one of the subvectors be augmented by adding one or more variables to it. For the increase in the largest canonical correlation, Δr in the sample and Δ in the population, it is shown that √n(Δr − Δ) → DN(0, σ2) and a formula for σ2 is derived. 相似文献
11.
In this paper, we prove that any graph G with maximum degree , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000 相似文献
12.
Donglong Li Zhengde Dai Xuhong Liu 《Journal of Mathematical Analysis and Applications》2007,330(2):934-948
In this paper, the two-dimensional generalized complex Ginzburg–Landau equation (CGL)
ut=ρu−Δφ(u)−(1+iγ)Δu−νΔ2u−(1+iμ)|u|2σu+αλ1(|u|2u)+β(λ2)|u|2