Distance graphs with missing multiples in the distance sets

Given positive integers m, k, and s with m > ks, let D_m,k,s represent the set {1, 2, …, m} − {k, 2k, …, sk}. The distance graph G(Z, D_m,k,s) has as vertex set all integers Z and edges connecting i and j whenever |i − j| ∈ D_m,k,s. The chromatic number and the fractional chromatic number of G(Z, D_m,k,s) are denoted by χ(Z, D_m,k,s) and χf(Z, D_m,k,s), respectively. For s = 1, χ(Z, D_m,k,1) was studied by Eggleton, Erdős, and Skilton [6], Kemnitz and Kolberg [12], and Liu [13], and was solved lately by Chang, Liu, and Zhu [2] who also determined χf(Z, D_m,k,1) for any m and k. This article extends the study of χ(Z, D_m,k,s) and χf(Z, D_m,k,s) to general values of s. We prove χf(Z, D_m,k,s) = χ(Z, D_m,k,s) = k if m < (s + 1)k; and χf(Z, D_m,k,s) = (m + sk + 1)/(s + 1) otherwise. The latter result provides a good lower bound for χ(Z, D_m,k,s). A general upper bound for χ(Z, D_m,k,s) is obtained. We prove the upper bound can be improved to ⌈(m + sk + 1)/(s + 1)⌉ + 1 for some values of m, k, and s. In particular, when s + 1 is prime, χ(Z, D_m,k,s) is either ⌈(m + sk + 1)/(s + 1)⌉ or ⌈(m + sk + 1)/(s + 1)⌉ + 1. By using a special coloring method called the precoloring method, many distance graphs G(Z, D_m,k,s) are classified into these two possible values of χ(Z, D_m,k,s). Moreover, complete solutions of χ(Z, D_m,k,s) for several families are determined including the case s = 1 (solved in [2]), the case s = 2, the case (k, s + 1) = 1, and the case that k is a power of a prime. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 245–259, 1999     

Arc-disjoint in-trees in directed graphs

Given a directed graph D = (V,A) with a set of d specified vertices S = {s ₁,…, s _d } ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ _i=1 ^d f(s _i ) arc-disjoint in-trees denoted by T _i,1,T _i,2,…, for every i = 1,…,d such that T _i,1,…, are rooted at s _i and each T _i,j spans the vertices from which s _i is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case. Supported by JSPS Research Fellowships for Young Scientists. Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan.     

Coloring of distance graphs with intervals as distance sets

Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form D_m,[k,k^′]={1,2,…,m}−{k,k+1,…,k^′}, where m, k, and k^′ are natural numbers with m≥k^′≥k. In particular, we completely determine the chromatic number of G(Z,D_m,[2,k^′]) for arbitrary m, and k^′.     

Hadwiger number and chromatic number for near regular degree sequences

We consider a problem related to Hadwiger's Conjecture. Let D=(d₁, d₂, …, d_n) be a graphic sequence with 0?d₁?d₂?···?d_n?n?1. Any simple graph G with D its degree sequence is called a realization of D. Let R[D] denote the set of all realizations of D. Define h(D)=max{h(G): G∈R[D]} and χ(D)=max{χ(G): G∈R[D]}, where h(G) and χ(G) are Hadwiger number and chromatic number of a graph G, respectively. Hadwiger's Conjecture implies that h(D)?χ(D). In this paper, we establish the above inequality for near regular degree sequences. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 175–183, 2010     

The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f ₁, f ₂, …, f _d } of distinct Roman k-dominating functions on G with the property that Σ _i=1 ^d f _i (v) ≤ 2 for each v ∈ V (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d _kR (G). Note that the Roman 1-domatic number d _1R (G) is the usual Roman domatic number d _R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d _kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.     

Measurable sets with excluded distances

For a set of distances $D=\{d_1,\dots ,d_k\}$ a set A in the plane is called D-avoiding if no pair of points of A is at distance $d_i$ for some i. We show that the density of A is exponentially small in k provided the ratios $d_1/d_2,d_2/d_3,\dots ,d_{k-1}/d_k$ are all small enough. We also show that there exists a largest D-avoiding set, and give an algorithm to compute the maximum density of a D-avoiding set for any D.     

On number system constructions

We investigate various number system constructions. After summarizing earlier results we prove that for a given lattice Λ and expansive matrix M: Λ → Λ if ρ(M ⁻¹) < 1/2 then there always exists a suitable digit set D for which (Λ, M, D) is a number system. Here ρ means the spectral radius of M ⁻¹. We shall prove further that if the polynomial f(x) = c ₀ + c ₁ x + ··· + c _k x ^k ∈ Z[x], c _k = 1 satisfies the condition |c ₀| > 2 Σ _i=1 ^k |c _i | then there is a suitable digit set D for which (Z ^k , M, D) is a number system, where M is the companion matrix of f(x). The research was supported by OTKA-T043657 and Bolyai Fellowship Committee.     

The 6-relaxed game chromatic number of outerplanar graphs

Suppose G is a graph and k,d are integers. The (k,d)-relaxed colouring game on G is a game played by two players, Alice and Bob, who take turns colouring the vertices of G with legal colours from a set X of k colours. Here a colour i is legal for an uncoloured vertex x if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Alice’s goal is to have all the vertices coloured, and Bob’s goal is the opposite: to have an uncoloured vertex without a legal colour. The d-relaxed game chromatic number of G, denoted by , is the least number k so that when playing the (k,d)-relaxed colouring game on G, Alice has a winning strategy. This paper proves that if G is an outerplanar graph, then for d≥6.     

The postage stamp problem and arithmetic in base <Emphasis Type="Italic">r</Emphasis>

Let h, k be fixed positive integers, and let A be any set of positive integers. Let hA ≔ {a ₁ + a ₂ + ... + a _r : a _i ∈ A, r ⩽ h} denote the set of all integers representable as a sum of no more than h elements of A, and let n(h, A) denote the largest integer n such that {1, 2,...,n} ⊆ hA. Let n(h, k) := : n(h, A), where the maximum is taken over all sets A with k elements. We determine n(h, A) when the elements of A are in geometric progression. In particular, this results in the evaluation of n(h, 2) and yields surprisingly sharp lower bounds for n(h, k), particularly for k = 3.     

Points surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

Packing nearly-disjoint sets

De Bruijn and Erdős proved that ifA ₁, ...,A _k are distinct subsets of a set of cardinalityn, and |A _i ∩A _j |≦1 for 1≦i<j ≦k, andk>n, then some two ofA ₁, ...,A _k have empty intersection. We prove a strengthening, that at leastk /n ofA ₁, ...,A _k are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary. Partially supported by N. S. F. grant No. MCS—8103440     

Chromatic uniqueness of certain complete tripartite graphs

Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k ²/4 + i + 1.     

A Generalisation of Tverberg’s Theorem

We will prove the following generalisation of Tverberg’s Theorem: given a set S⊂ℝ ^d of (r+1)(k−1)(d+1)+1 points, there is a partition of S in k sets A ₁,A ₂,…,A _k such that for any C⊂S of at most r points, the convex hulls of A ₁\C,A ₂\C,…,A _k \C are intersecting. This was conjectured first by Natalia García-Colín (Ph.D. thesis, University College of London, 2007).     

Disk-like Tiles Derived from Complex Bases

For each positive integer k, the radix representation of the complex numbers in the base –k+i gives rise to a lattice self-affine tile T _k in the plane, which consists of all the complex numbers that can be expressed in the form ∑ _j≥1 d _j (–k+i)^–j , where d _j ∈{0, 1, 2, ...,k ²}. We prove that T _k is homeomorphic to the closed unit disk {z∈C:∣z∣ ≤ 1} if and only if k ≠ 2. The first author is supported by Youth Project of Tianyuan Foundation (10226031) and Zhongshan University Promotion Foundation for Young Teachers (34100-1131206); the second author is supported by National Science Foundation (10041005) and Guangdong Province Science Foundation (011221)     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

An exact Turán result for the generalized triangle

Let Σ _k consist of all k-graphs with three edges D ₁, D ₂, D ₃ such that |D ₁ ∩ D ₂| = k − 1 and D ₁ Δ D ₂ ⊆ D ₃. The exact value of the Turán function ex(n, Σ _k ) was computed for k = 3 by Bollobás [Discrete Math. 8 (1974), 21–24] and for k = 4 by Sidorenko [Math Notes 41 (1987), 247–259]. Let the k-graph T _k ∈ Σ _k have edges

Degree sets ofk-trees: Smallk

Ak-tree is ak-uniform hypergraph constructed from a single edge by the successive addition of edges each containing a new vertex andk−1 vertices of an existing edge. We show that ifD is any finite set of positive integers which includes 1, thenD is the set of vertex degrees of somek-tree fork=2, 3, and 4, and that there is precisely one such set,D={1, 4, 6}, which is not the set of degrees of any 5-tree. We also show for eachk≧2 that such a setD is the set of degrees of somek-tree provided only thatD contains some elementd which satisfiesd≧k (k−1)−2 [k/2]+3.     

Local linear operators and multicontour solutions of homogeneous coupled map lattices

Theorems are proved establishing a relationship between the spectra of the linear operators of the formA+Ωg _iB_ig_i ⁻¹ andA+B _i, whereg _i∈G, andG is a group acting by linear isometric operators. It is assumed that the closed operatorsA andB _i possess the following property: ‖B _iA⁻¹gB_jA⁻¹‖→0 asd(e,g)→∞. Hered is a left-invariant metric onG ande is the unit ofG. Moreover, the operatorA is invariant with respect to the action of the groupG. These theorems are applied to the proof of the existence of multicontour solutions of dynamical systems on lattices. Translated fromMatematicheskie Zametki, Vol. 65, No. 1, pp. 37–47, January, 1999.     

Sur le 2-groupe de classes d'idéaux de ℚ(√d,i)

Let ℕ,i=√−1,k=ℚ(√d,i) andC ₂ the 2-part of the class group ofk. Our goal is to determine alld such thatC ₂⋍ℤ/2ℤ×ℤ/2ℤ. Soientd∈ℕ,i=√−1,k=ℚ(√d,i), etC ₂ la 2-partie du groupe de classes dek. On s'intéresse à déterminer tous lesd tel queC ₂⋍ℤ/2ℤ×ℤ/2ℤ.