On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

An extension theorem for t-designs

In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an S_λ(t,k,v) such that

then there exists an S_λ(v−t+1)(t,k,v+1) having v+1 pairwise disjoint subdesigns S_λ(t,k,v). Moreover, if B_i and B_j are any two blocks belonging to two distinct such subdesigns, then d|B_i∩B_j|<k−h. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an S_λ(t,k,v) such that

where m=min{s,v−k} and n=min{i,t}, then there exists an

having pairwise disjoint subdesigns S_λ(t,k,v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs.     

Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ₁. We consider the power method, i.e. that of choosing a vector v₀ and setting v_k = A^kv₀; then the Rayleigh quotients R_k = (Av_k, v_k)/(v_k, v_k) usually converge to λ₁ as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close R_k is to λ₁. They are both based on a bound on λ₁ − R_k involving the difference of two consecutive Rayleigh quotients and a quantity ω_k. While we do not know how to directly calculate ω_k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ₁ − R_k which is proportional to (λ₂/λ₁)^2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).     

k-Subdomination in graphs

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).     

On the use of augmenting chains in chain packings

In a graph G = (X, E), we assign to each node υ a positive integer b(υ)≤d_G(υ), where d_G(υ) is the degree of υ in G. Let P be a collection of edge-disjoint chains such that no two chains in P have a common endpoint and such that in the partial graph H = (X, E(P)) formed by the edge set E(P) of P we have d_H(υ)≤b(υ) for each node υ. P is called a chain packing.

We extend the augmenting chain theorem of matchings to chain packings and we find an analogue of matching matroids. We also study chain packings by short chains, i.e., chains of lengths one or two. We show that we may restrict ourselves to packings by short chains when we want to find a packing containing a maximum number of chains. We show that the use of augmenting chains fails in general to produce a new short chain packing from an old one, even for bipartite graphs, but that it does do so for the special case of trees. For the case of trees, we also find a min-max result for packings by short chains.     

Magic Labeling of Disjoint Union Graphs

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 ∈ E_v, f(e) ≤ Δ/2}|=|{e:e ∈ E_v, 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 (2m + 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.     

Sum coloring and interval graphs: a tight upper bound for the minimum number of colors

The SUM COLORING problem consists of assigning a color c(v_i)Z⁺ to each vertex v_iV of a graph G=(V,E) so that adjacent nodes have different colors and the sum of the c(v_i)'s over all vertices v_iV is minimized. In this note we prove that the number of colors required to attain a minimum valued sum on arbitrary interval graphs does not exceed min{n;2χ(G)−1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight.     

An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

Every tree is 3-equitable

A labeling of a graph is a function f from the vertex set to some subset of the natural numbers. The image of a vertex is called its label. We assign the label |f(u)−f(v)| to the edge incident with vertices u and v. In a k-equitable labeling the image of f is the set {0,1,2,…,k−1}. We require both the vertex labels and the edge labels to be as equally distributed as possible, i.e., if v_i denotes the number of vertices labeled i and e_i denotes the number of edges labeled i, we require |v_i−v_j|1 and |e_i−e_j|1 for every i,j in {0,1,2,…,k−1}. Equitable graph labelings were introduced by I. Cahit as a generalization for graceful labeling. We prove that every tree is 3-equitable.     

The smallest degree sum that yields potentially kCℓ-graphic sequences

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 π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(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 π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(_kC_ℓ,n) has a realization G containing a cycle of length r for each r, krℓ.     

A generalization of carathéodory''s theorem

The following theorem is proved. If the sets and a εⁿ⁺¹_i=1 conv V_i, then there exist elements v_i ε V_i (i=1…,n+1) such that a ε conv{v₁,…,v_n+1}. This is generalization of Carathéodory's theorem. By applying this and similar results some open questions are answered.     

A note on a property of a weak self-similar perfect set

Let S be a compact, weak self-similar perfect set based on a system of weak contractions f_j, j=1,…,m each of which is characterized by a variable contraction coefficient _j(l) as d(f_j(x),f_j(y)) _j(l)d(x,y), d(x,y)<l, l>0. If the relation ∑^m_j=1j(l₀)<1 holds at at least one point l₀, then every nonempty compact metric space is a continuous image of the set S.     

C-normality and solvability of groups

A subgroup H is called c-normal in group G if there exists a normal subgroup N and G such that HN = G and H ∩ N ≤ H_G where H_G =: Core(H) = _gG H^g is the maximal normal subgroup of G which is contained in H. We obtain some results about the c-normal subgroups and the solvability of groups.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<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 |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

Multicolor routing in the undirected hypercube

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 Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/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 (Q_n,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.     

Graph rigidity via Euclidean distance matrices

Let G=(V,E,ω) be an incomplete graph with node set V, edge set E, and nonnegative weights ω_ij's on the edges. Let each edge (v_i,v_j) be viewed as a rigid bar, of length ω_ij, which can rotate freely around its end nodes. A realization of a graph G is an assignment of coordinates, in some Euclidean space, to each node of G. In this paper, we consider the problem of determining whether or not a given realization of a graph G is rigid. We show that each realization of G can be epresented as a point in a compact convex set ; and that a generic realization of G is rigid if and only if its corresponding point is a vertex of Ω, i.e., an extreme point with full-dimensional normal cone.     

Some peculiar boundary phenomena for extremes of rth nearest neighbor links

Let D_n,r denote the largest rth nearest neighbor link for n points drawn independently and uniformly from the unit d-cube C_d. We show that according as r < d or r>d, the limiting behavior of D_n,r, as n → ∞, is determined by the two-dimensional ‘faces’ respectively one-dimensional ‘edges’ of the boundary of C_d. If d = r, a ‘balance’ between faces and edges occurs. In case of a d-dimensional sphere (instead of a cube) the boundary dominates the asymptotic behavior of D_n,r if d 3 or if d = 2, r 3.     

Coupling and harmonic functions in the case of continuous time Markov processes

Consider two transient Markov processes (X^v_t)_tεR·, (X^μ_t)_tεR· with the same transition semigroup and initial distributions v and μ. The probability spaces supporting the processes each are also assumed to support an exponentially distributed random variable independent of the process.

We show that there exist (randomized) stopping times S for (X^v_t), T for (X^μ_t) with common final distribution, L(X^v_S|S < ∞) = L(X^μ_T|T < ∞), and the property that for t < S, resp. t < T, the processes move in disjoint portions of the state space. For such a coupling (S, T) it is shown

where denotes the bounded harmonic functions of the Markov transition semigroup. Extensions, consequences and applications of this result are discussed.     

Bandwidth of the composition of two graphs

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 (u₁,v₁) is adjacent to (u₂,v₂) if either u₁ is adjacent to u₂ in G or u₁=u₂ and v₁ is adjacent to v₂ 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 w_G(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 w_G(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.