共查询到20条相似文献,搜索用时 171 毫秒
1.
图 G的正常[ k]-边染色 σ是指颜色集合为[ k]={1,2,…, k}的 G的一个正常边染色.用 wσ( x)表示顶点 x关联边的颜色之和,即 wσ( x)=∑ e∋x σ( e),并称 wσ( x)关于 σ的权.图 G的 k-邻和可区别边染色是指相邻顶点具有不同权的正常[ k]-边染色,最小的 k值称为 G的邻和可区别边色数,记为 χ' ∑( G).现得到了路 Pn与简单连通图 H的字典积 Pn[ H]的邻和可区别边色数的精确值,其中 H分别为正则第一类图、路、完全图的补图. 相似文献
2.
For each positive integer k we consider the smallest positive integer f( k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ( G) = k can be properly vertex colored by k colors so that for each pair of vertices xo and xp in any color class there exist vertices x1, x2, …, xp-1 of the same class with dist( xi, xi+1) f( k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f( k) from the remainder of the class. We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1. 相似文献
3.
An undirected routing problem is a pair ( G, R) where G is an undirected graph and R is an undirected multigraph such that V( G)= V( R). A solution to an undirected routing problem ( G, R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge { u, v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Qn denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem ( Qn, R) always admits a 4 d-colorable solution where d is the maximum vertex degree of R. This improves over the 16 d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to ( Qn, R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors. 相似文献
4.
For a graph G of size m1 and edge-induced subgraphs F and H of size k (1 km), 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 1 km, 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. 相似文献
5.
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. 相似文献
6.
Let G be a plane graph, and let χ k( G) be the minimum number of colors to color the vertices of G so that every two of them which lie in the boundary of the same face of the size at most k, receive different colors. In 1966, Ore and Plummer proved that χ k( G)2 k for any k3. It is also known that χ 3( G)4 (Appel and Haken, 1976) and χ 4( G)6 (Borodin, 1984). The result in the present paper is: χ 5( G)9, χ 6( G)11, χ 7( G)12, and χ k( G)2 k − 3 if k8. 相似文献
7.
Let G be a graph of maximum degree Δ. A proper vertex coloring of G is acyclic if there is no bichromatic cycle. It was proved by Alon et al. [Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277−288] that G admits an acyclic coloring with O(Δ 4/3) colors and a proper coloring with O(Δ (k−1)/(k−2)) colors such that no path with k vertices is bichromatic for a fixed integer k≥5. In this paper, we combine above two colorings and show that if k≥5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Δ (k−1)/(k−2)) colors such that no path with k vertices is bichromatic. 相似文献
8.
We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G; x) :=∑?(G)k=-nB_k(G) x~(n+k), where B_k(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G;x) and its coefficients.In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G. 相似文献
9.
Let G be a graph of order n, and let a and b be integers such that 1 a< b. Let δ( G) be the minimum degree of G. Then we prove that if δ( G)( k−1) a, n( a+ b)( k( a+ b)−2)/ b, and | NG( x1) NG( x2) NG( xk)| an/( a+ b) for any independent subset { x1, x2,…, xk} of V( G), where k2, then G has an [ a, b]-factor. This result is best possible in some sense. 相似文献
10.
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. 相似文献
11.
Let G be a graph with vertex set V ( G), edge set E( G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …,| E( G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to (1+| E( G)|)/2· d( v), where d( v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V ( G),|{ e:e ∈ Ev, f( e) ≤ Δ/2}|=|{ e:e ∈ Ev, f( e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2 m + 1) G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results. 相似文献
12.
The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V1, V2,…, Va such that for each i at most d vertices in V1 … Vi have neighbors in Vi+1 and r( Kk, Vi) p | V( G) |, where Vi denotes the subgraph of G induced by Vi. Then there exists a number c depending only on p, d, and k such that r( Kk, G) c | V( G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V( G) such that each component of G− I has at most d vertices and at most two neighbors in I. Then r( G, G) c | V( G) |, where c is a number depending only on d. As a special case, r( G, G) 6 | V( G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4. 相似文献
13.
In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ k( G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ k( T)= n/( k+1) when T is a tournament with n14 k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices. 相似文献
14.
Consider a graph G and a k-uniform hypergraph
on common vertex set [ n]. We say that
is G-intersecting if for every pair of edges in
there are vertices xX and yY such that x= y or x and y are joined by an edge in G. This notion was introduced by Bohman, Frieze, Ruszinkó and Thoma who proved a natural generalization of the Erd
s–Ko–Rado Theorem for G-intersecting k-uniform hypergraphs for G sparse and k=O( n1/4). In this note, we extend this result to
. 相似文献
15.
For a positive integer k, a k-subdominating function of a graph G=( V, E) is a function f : V→{−1,1} such that ∑ uNG[v]f( u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ ks( G), is the minimum of ∑ vVf( v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ ks( G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ ks( G), the signed domination number γ s( G) and the majority domination number γ maj( G). 相似文献
16.
An L(2,1)- coloring of a graph G is a coloring of G's vertices with integers in {0,1,…, k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ( G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ( G), and the hole index ρ( G) of G is the minimum number of colors in {0,1,…,λ( G)} not used in a span coloring. We say that G is full-colorable if ρ( G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ( G) of G as ∞ if G has no no-hole coloring; otherwise μ( G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…, k}. Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m. 相似文献
17.
Let G be a k-regular vertex transitive graph with connectivity κ( G)= k and let mk( G) be the number of vertex cuts with k vertices. Define m(n,k)=min {mk(G): GTn,k}, where Tn,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ( G)= k. In this paper, we determine the exact values of m( n, k). 相似文献
18.
The following problem is considered: given: an undirected planar graph G=( V, E) embedded in
, distinct pairs of vertices { r1, s1},…,{ rk, sk} of G adjacent to the unbounded face, positive integers b1,…, bk and a function
; find: pairwise vertex-disjoint paths P1,…, Pk such that for each i=1,…, k, Pi is a ri− si-path and the sum of the l-length of all edges in Pi is at most bi. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2. 相似文献
19.
This paper is the first article in a series devoted to the study of the following general problem on vertex colorings of graphs. Suppose that some vertices of a graph G are assigned to some colors. Can this ‘precoloring’ be extended to a proper coloring of G with at most k colors (for some given k)? This question was motivated by practical problems in scheduling and VLSI theory. Here we investigate its complexity status for interval graphs and for graphs with a bounded treewidth. 相似文献
20.
For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E( F), wx ε E( G) - E( F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J( G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J( G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{ Jk( G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence. 相似文献
|