共查询到20条相似文献,搜索用时 375 毫秒
1.
给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ'(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。在图G中,如果mad(G) < 3并且Δ≤4,那么χ'(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ'(1,0)(G)≤3Δ-1。 相似文献
2.
G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G1,G2,且|G1|≥2,|G2|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t> $ \frac{k}{2}$ 的整数,若G是一个不含(K2+tK1)的k-连通图,且G中任意两个不同点对v,w,有d(v)+d(w)≥ $\frac{{3k}}{2} $ +t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有$\frac{{\left| {V\left( G \right)} \right|}}{2} $ 条边使得收缩其中任意一条边后仍是拟k-连通的。 相似文献
3.
4.
假设G=(V,E,F)是一个平面图。如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ vef(G)。2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。 相似文献
5.
图G的正常边染色f满足相邻点的色集合相不互包含时,该染色称为图G的Smarandcchely-邻点可区别边染色,其中S(x)={f(xw)|xw∈E(G)}称之为在f下的顶点x的色集合.该染色称为图G的Smarandchely-邻点可区别边染色.对图G进行的.Smarandchely-邻点可区别边染色所用最少颜色数称为图G的Smarandachely-邻点可区别边色数.讨论了Pm□Pn的Smarandchely-邻点可区别边色数. 相似文献
6.
《数学的实践与认识》2013,(23)
图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.图G的邻点可区别无圈边色数记为χ′_(aa)(G),即图G的一个邻点可区别无圈边染色所用的最少颜色数.通过构造具体染色的方法,给出了一些k-方图的邻点可区别无圈边色数. 相似文献
7.
8.
杨随义 《数学的实践与认识》2023,(5):142-152
图G的邻点可区别Ⅰ-全染色是一个满足相邻顶点色集合不同的Ⅰ-全染色,其中任意一点的色集合包含该顶点及其关联边所染的颜色.所需颜色的最小数称为邻点可区别Ⅰ-全色数,记作χati(G).研究了路和圈的广义Mycielski图的邻点可区别Ⅰ-全色数:对于阶数n≥2的路Pn,当n=2,3,4时,有χati(M(Pn))=n+1;否则,χati(M(Pn))=n.对于阶数n≥3的圈Cn,当n=3,4时,有χati(M(Cn))=5;否则,χati(M(Cn))=n. 相似文献
9.
设G(V,E)是简单连通图,T(G)为图G的所有顶点和边构成的集合,并设C是k-色集(k是正整数),若T(G)到C的映射f满足:对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),并且C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.那么称f为图G的邻点可区别E-全染色(简记为k-AVDETC),并称χ_(at)~e(G)=min{k|图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M(G)就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数. 相似文献
10.
《数学的实践与认识》2015,(10)
提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标. 相似文献
11.
A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ'_s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2 k. Yang and Zhu [J. Graph Theory, 83, 334–339(2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1. 相似文献
12.
Let σ={σi|i∈I} be some partition of the set of all primes P, G a finite group and σ(G)={σi|σi ∩ π(G)≠∅}. A set H of subgroups of G is said to be a complete Hall σ-set of G if every member≠1 of H is a Hall σi-subgroup of G for some σi ∈ σ and H contains exactly one Hall σi-subgroup of G for every σi ∈ σ(G). A subgroup H of G is said to be:σ-semipermutable in G with respect to H if HHix=HixH for all x ∈ G and all Hi ∈ H such that (|H|,|Hi|)=1; σ-semipermutable in G if H is σ-semipermutable in G with respect to some complete Hall σ-set of G. We study the structure of G being based on the assumption that some subgroups of G are σ-semipermutable in G. 相似文献
13.
The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[H], is the graph with vertex set V(G)×V(H) and with (u1,v1) is adjacent to (u2,v2) if either u1 is adjacent to u2 in G or u1=u2 and v1 is adjacent to v2 in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D(G). For two distinct vertices x,yV(G), we define wG(x,y) as the maximum number of internally vertex-disjoint (x,y)-paths whose lengths are the distance between x and y. We define w(G) as the minimum of wG(x,y) over all pairs of vertices x,y of G with the distance between x and y is equal to D(G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if |V(G)|=B(G)D(G)−w(G)+2, then B(G[H])=(B(G)+1)|V(H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph. 相似文献
14.
For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph Jk(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of Jk(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J2(G) is planar are determined. 相似文献
15.
If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a1,a2,…,ak), in which ai denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph Kn,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of Kn,n into multicolored trees. 相似文献
16.
Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals 下载免费PDF全文
Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I. 相似文献
17.
Solution to an extremal problem on bigraphic pairs with a <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connected realization 下载免费PDF全文
Let S=(a1,...,am; b1,...,bn), where a1,...,am and b1,...,bn are two nonincreasing sequences of nonnegative integers. The pair S=(a1,...,am; b1,...,bn) is said to be a bigraphic pair if there is a simple bipartite graph G=(X ∪ Y, E) such that a1,...,am and b1,...,bn are the degrees of the vertices in X and Y, respectively. Let Z3 be the cyclic group of order 3. Define σ(Z3, m, n) to be the minimum integer k such that every bigraphic pair S=(a1,...,am; b1,...,bn) with am, bn ≥ 2 and σ(S)=a1 +... + am ≥ k has a Z3-connected realization. For n=m, Yin[Discrete Math., 339, 2018-2026 (2016)] recently determined the values of σ(Z3, m, m) for m ≥ 4. In this paper, we completely determine the values of σ(Z3, m, n) for m ≥ n ≥ 4. 相似文献
18.
Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(kCℓ,n) such that each n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(kCℓ,n) has a realization G containing a cycle of length r for each r, krℓ. 相似文献
19.
A random graph Gn(x) is constructed on independent random points U1,…,Un distributed uniformly on [0,1]d, d1, in which two distinct such points are joined by an edge if the l∞-distance between them is at most some prescribed value 0<x<1. The connectivity distance cn, the smallest x for which Gn(x) is connected, is shown to satisfy For d2, the random graph Gn(x) behaves like a d-dimensional version of the random graphs of Erdös and Rényi, despite the fact that its edges are not independent: cn/dn→1, a.s., as n→∞, where dn is the largest nearest-neighbor link, the smallest x for which Gn(x) has no isolated vertices. 相似文献
20.
Let H be a Hopf algebra over a field k and let H A → A, h a → h.a, be an action of H on a commutative local Noetherian kalgebra (A, m). We say that this action is linearizable if there exists a minimal system x1, …, xn of generators of the maximal ideal m such that h.xi ε kx1 + …+ kxn for all h ε H and i = 1, …, n. In the paper we prove that the actions from a certain class are linearizable (see Theorem 4), and we indicate some consequences of this fact. 相似文献