Search

We consider special distance graphs and estimate the number of edges in their subgraphs. The estimates obtained improve some known results. [ABSTRACT FROM AUTHOR]

We study polytopes defined by inequalities of the form ∑ i ∈ I z i ≤ 1 for I ⊆ [ d ] and nonnegative z i where the inequalities can be reordered into a matrix inequality involving a column-convex { 0 , 1 } -matrix. These generalize polytopes studied by Stanley, and the consecutive coordinate polytopes of Ayyer, Josuat-Vergès, and Ramassamy. We prove an integral equivalence between these polytopes and flow polytopes of directed acyclic graphs G with a Hamiltonian path, which we call spinal graphs. We show that the volumes of these flow polytopes are given by the number of upper (or lower) G-cyclic orders defined by the graphs G. As a special case we recover results on volumes of consecutive coordinate polytopes. We study the combinatorics of k-Euler numbers, which are generalizations of the classical Euler numbers, and which arise as volumes of flow polytopes of a special family of spinal graphs. We show that their refinements, Ramassamy's k-Entringer numbers, can be realized as values of a Kostant partition function, satisfy a family of generalized boustrophedon recurrences, and are log concave along root directions. Finally, via our main integral equivalence and the known formula for the h ∗ -polynomial of consecutive coordinate polytopes, we give a combinatorial formula for the h ∗ -polynomial of flow polytopes of non-nested spinal graphs. For spinal graphs in general, we present a conjecture on upper and lower bounds for their h ∗ -polynomial. [ABSTRACT FROM AUTHOR]

Let M be a set of positive integers. We study the maximal density μ(M) of the sets of nonnegative integers S whose elements do not differ by an element in M. In 1973, Cantor and Gordon established a formula for μ(M) for |M| ≤ 2. Since then, many researchers have worked upon the problem and found several partial results in the case |M| ≥ 3, including some results in the case when M is an infinite set. In this paper, we study the maximal density problem for the families M = {a, a+1, 2a+1, n} and M = {a, a+1, 2a+1, 3a+1, n}, where a and n are positive integers and n is sufficiently large. In most of the cases, we find bounds for the parameter kappa, denoted by κ(M), which actually serves as a lower bound for μ(M). The parameter κ(M) has already got its importance due to its rich connection with problems such as the "lonely runner conjecture" in Diophantine approximation and coloring parameters such as "circular coloring" and "fractional coloring" in graph theory. We also give some partial results for the general family M = {a, a +1, 2a + 1,..., (s – 2)a + 1, n}, where s ≥ 5 and mention related problems in the remaining cases for future work. [ABSTRACT FROM AUTHOR]

A graph G(Z, D) with vertex set Z is called an integer distance graph if its edge set is obtained by joining two elements of Z by an edge whenever their absolute difference is a member of D. When D = P or D ⊆ P where P is the set of all prime numbers then we call it a prime distance graph. After establishing the chromatic number of G(Z, P) as four, Eggleton has classified the collection of graphs as belonging to class i if the chromatic number of G(Z, D) is i. The problem of characterizing the family of graphs belonging to class i when D is of any given size is open for the past few decades. As coloring a prime distance graph is equivalent to producing a prime distance labeling for vertices of G, we have succeeded in giving a prime distance labeling for certain class of all graphs considered here. We have proved that if D = {2, 3, 5, 7, 7th prime, 10th prime, 13th prime, 16th prime, (7 + Ps-1 j=1 4 ×3j)th prime, . . ., (4 + Ps j=1 4 × 3j)th prime for any s ∈ N}, then there exists a prime distance graph with distance set D in class 4 and if D = {2, 3, 5, 4th prime, 6th prime, 8th prime, (4 + Ps-1 j=1 3 × 2j)th prime, . . ., (2 + Ps j=1 3 × 2j)th prime for any s ∈ N} then there exists a prime distance graphs with distance set D in class 3. Further, we have also obtained some more interesting results that are either general or existential such as a) If D is a specific sequence of integers in arithmetic progression then there exist a prime distance graph with distance set D, b) If G is any prime distance graph in class i for 1 ≤ i ≤ 4 then G × K2 is also a prime distance graph in the respective class i, c) A countable union of disjoint copies of prime distance graph is again a prime distance graph, d) The Middle/Total graph of a path on n vertices is a prime distance graph. In addition we also provide a new different proof for establishing a fact that all cycles are prime distance graph. [ABSTRACT FROM AUTHOR]

A radio k -labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that the absolute value of the difference between the labels of any two distinct vertices u and v is not less than k + 1 − d (u , v) , where d (u , v) denotes the distance between u and v. The radio k -labeling number of G is the minimum span of a radio k -labeling of G. For a given set of integers D = { d 1 , d 2 , ... , d t } , the distance graph G (Z , D) , denoted also by D (d 1 , d 2 , ... , d t) , has the set of integers Z as its vertex set, while two distinct vertices i , j ∈ Z are adjacent in G (Z , D) if and only if | i − j | ∈ D. Radio k -labelings of three families of distance graphs are considered. Some improved theoretical lower and upper bounds on the radio k -labeling number are presented and some computer-based methods for computing radio k -labelings of these families of graphs are proposed. [ABSTRACT FROM AUTHOR]

Given a graph G and a non-decreasing sequence S = (a 1 , a 2 , ...) of positive integers, the mapping f : V (G) → { 1 , ... , k } is an S -packing k -coloring of G if for any distinct vertices u , v ∈ V (G) with f (u) = f (v) = i the distance between u and v in G is greater than a i. The smallest k such that G has an S -packing k -coloring is the S -packing chromatic number, χ S (G) , of G. In this paper, we continue the study of S -packing colorings of distance graphs, initiated by Togni (2014) and Ekstein et al. (2012). We focus on the distance graphs G (Z , { 2 , t }) , where t > 1 is an odd integer, which has Z as its vertex set, and i , j ∈ Z are adjacent if | i − j | ∈ { 2 , t }. We determine the S -packing chromatic numbers of the graphs G (Z , { 2 , t }) , where S is any sequence with a i ∈ { 1 , 2 } for all i. In addition, we give lower and upper bounds for the d -distance chromatic numbers of the distance graphs G (Z , { 2 , t }) , which in the cases d ≥ t − 3 give the exact values. Implications for the corresponding S -packing chromatic numbers of the circulant graphs are also discussed. [ABSTRACT FROM AUTHOR]

Given a measurable set A ⊂ R d we consider the large-distance graph G A , on the ground set A, in which each pair of points from A whose distance is bigger than 2 forms an edge. We consider the problems of maximizing the 2d-dimensional Lebesgue measure of the edge set as well as the d-dimensional Lebesgue measure of the vertex set of a large-distance graph in the d-dimensional Euclidean space that contains no copies of a complete graph on k vertices. The former problem may be seen as a continuous analogue of Turán's classical graph theorem, and the latter as a "graph-theoretic" analogue of the classical isodiametric problem. Our main result yields an analogue of Mantel's theorem for large-distance graphs. Our approach employs an isodiametric inequality in an annulus, which might be of independent interest. [ABSTRACT FROM AUTHOR]

For a given set M of positive integers, a well-known problem of Motzkin asks to determine the maximal asymptotic density of M-sets, denoted by μ(M), where an M-set is a set of non-negative integers in which no two elements differ by an element in M. In 1973, Cantor and Gordon find μ(M) for |M| ≤ 2. Partial results are known in the case |M| ≥ 3 including some results in the case when M is an infinite set. Motivated by some 3 and 4-element families already discussed by Liu and Zhu in 2004, we study μ(M) for two families namely, M = {a, b,a + b, n(a + b)} and M = {a, b, b − a, n(b − a)}. For both of these families, we find some exact values and some bounds on μ(M). This number theory problem is also related to various types of coloring problems of the distance graphs generated by M. So, as an application, we also study these coloring parameters associated with these families. [ABSTRACT FROM AUTHOR]

We prove the existence in rational spaces of distance graphs without short odd cycles whose chromatic number increases exponentially with the dimension of the space. [ABSTRACT FROM AUTHOR]

We study the asymptotic behavior of the independence number of a random subgraph of a certain (r, s)-distance graph. We provide upper and lower bounds for the critical edge survival probability under which a phase transition occurs, i.e., large new independent sets appear in the subgraph, which did not exist in the original graph. [ABSTRACT FROM AUTHOR]

For positive integers n > r > s, G(n, r, s) is the graph whose vertices are the r-element subsets of an n-element set, two subsets being adjacent if their intersection contains exactly s elements. We study the chromatic numbers of this family of graphs. In particular, the exact value of the chromatic number of G(n, 3, 2) is found for infinitely many n. We also improve the best known upper bounds for chromatic numbers for many values of the parameters r and s and for all sufficiently large n. [ABSTRACT FROM AUTHOR]

We derive an analog of the Frankl-Wilson theorem on independence numbers of some distance graphs. The obtained results are applied to the problem of the chromatic number of a space ℝn with a forbidden equilateral triangle and to the problem of chromatic numbers of distance graphs with large girth. [ABSTRACT FROM AUTHOR]

This paper considers the so-called distance graph G(n, r, s);its vertices can be identified with the r-element subsets of the set {1, 2,...,n}, and two vertices are joined by an edge if the size of the intersection of the corresponding subsets equals s. Note that, in the case s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erdős-Ko-Rado problem; they also play an important role in combinatorial geometry and coding theory. We study properties of random subgraphs of the graph G(n, r, s) in the Erdős-Rényi model, in which each edge is included in the subgraph with a certain fixed probability p independently of the other edges. It is known that if r > 2s + 1, then, for p = 1/2, the size of an independent set is asymptotically stable in the sense that the independence number of a random subgraph is asymptotically equal to that of the initial graph G(n, r, s). This gives rise to the question of how small p must be for asymptotic stability to cease. The main result of this paper is the answer to this question. [ABSTRACT FROM AUTHOR]

We study distance graphs with exponentially large chromatic number which do not contain cliques of prescribed size in the rational space. [ABSTRACT FROM AUTHOR]

Borsuk's celebrated conjecture, which has been disproved, can be stated as follows: in ℝn, there exist no diameter graphs with chromatic number larger than n + 1. In this paper, we prove the existence of counterexamples to Borsuk's conjecture which, in addition, have large girth. This study is in the spirit of O'Donnell and Kupavskii, who studied the existence of distance graphs with large girth. We consider both cases of strict and nonstrict diameter graphs. We also prove the existence of counterexamples with large girth to a statement of Lovász concerning distance graphs on the sphere. [ABSTRACT FROM AUTHOR]

We obtain new estimates for the number of edges in induced subgraphs of some distance graph. [ABSTRACT FROM AUTHOR]

A particular class of estimates related to the Nelson–Erdős–Hadwiger problem is studied. For two types of spaces, Euclidean and spaces with metric ℓ1, certain series of distance graphs of small dimensions are considered. Independence numbers of such graphs are estimated by using the linear-algebraic method and combinatorial observations. This makes it possible to obtain certain lower bounds for the chromatic numbers of the spaces mentioned above and, for each case, specify a series of graphs leading to the strongest results. [ABSTRACT FROM AUTHOR]

An explicit exponentially growing lower bound for the chromatic number of Euclidean space with forbidden regular simplex is constructed. [ABSTRACT FROM AUTHOR]

We obtain some specific exponential lower bounds for the chromatic numbers of distance graphs with large girth. [ABSTRACT FROM AUTHOR]

A graph G is embeddable in R d if the vertices of G can be assigned to points of R d in such a way that all pairs of adjacent vertices are at distance 1. We show that verifying embeddability of a given graph in R d is NP-hard in the case d > 2 for all reasonable notions of embeddability. [ABSTRACT FROM AUTHOR]

The paper studies the distribution of the number of copies of fixed graphs in random subgraphs of graphs that play a key role in solving various problems of combinatorial geometry. As a corollary of the obtained results, we find a threshold function for planarity of a random subgraph of a distance graph, which is interesting in the context of random subgraphs of arbitrary regular graphs as well. [ABSTRACT FROM AUTHOR]

We obtain new estimates for the number of edges in induced subgraphs of a special distance graph. [ABSTRACT FROM AUTHOR]

We consider the distance graph G( n, r, s), whose vertices can be identified with r-element subsets of the set {1, 2,..., n}, two arbitrary vertices being joined by an edge if and only if the cardinality of the intersection of the corresponding subsets is s. For s = 0, such graphs are known as Kneser graphs. These graphs are closely related to the Erdős-Ko-Rado problem and also play an important role in combinatorial geometry and coding theory. We study some properties of random subgraphs of G( n, r, s) in the Erdős-Rényi model, in which every edge occurs in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G( n, r, s) for the case of constant r and s. The independence number of a random subgraph is Θ(log n) times as large as that of the graph G( n, r, s) itself for r ≤ 2 s + 1, while for r > 2 s + 1 one has asymptotic stability: the two independence numbers asymptotically coincide. [ABSTRACT FROM AUTHOR]

We consider the so-called distance graph G( n, 3, 1), whose vertices can be identified with three-element subsets of the set {1, 2,..., n}, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of G( n, 3, 1) in the Erdős-Rényi model, in which each edge is included in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G( n, 3, 1). [ABSTRACT FROM AUTHOR]

The object of study is the graph with i.e., the vertices of the graph are r-subsets of the set R = {1, ..., n}, and two vertices are connected by an edge if these vertices intersect in precisely s elements. Two-sided estimates for the number of Hamiltonian paths in the graph G( n, k, 1) as n → ∞ are obtained. [ABSTRACT FROM AUTHOR]

This paper is related to the classical Hadwiger-Nelson problem dealing with the chromatic numbers of distance graphs in ℝ. We consider the class consisting of the graphs G( n, 2 s + 1, s) = ( V ( n, 2 s + 1), E( n, 2 s + 1, s)) defined as follows: where ( x, y) stands for the inner product. We study the random graph G(G( n, 2 s + 1, s), p) each of whose edges is taken from the set E( n, 2 s+1, s) with probability p independently of the other edges. We prove a new bound for the chromatic number of such a graph. [ABSTRACT FROM AUTHOR]

Upper bounds for the independence numbers in the graphs with vertices at {−1, 0, 1} are improved. Their applications to problems of the chromatic numbers of distance graphs are studied. [ABSTRACT FROM AUTHOR]

Abstract: The packing chromatic number of a graph is the least integer for which there exists a mapping from to such that any two vertices of color are at a distance of at least . This paper studies the packing chromatic number of infinite distance graphs , i.e. graphs with the set of integers as vertex set, with two distinct vertices being adjacent if and only if . We present lower and upper bounds for , showing that for finite , the packing chromatic number is finite. Our main result concerns distance graphs with for which we prove some upper bounds on their packing chromatic numbers, the smaller ones being for : if is odd and if is even. [Copyright &y& Elsevier]

Abstract: The packing chromatic number of a graph is the smallest integer such that vertices of can be partitioned into disjoint classes where vertices in have pairwise distance between them greater than . For we study the packing chromatic number of infinite distance graphs , i.e. graphs with the set of integers as vertex set and in which two distinct vertices are adjacent if and only if . We generalize results given by Ekstein et al. for graphs . For sufficiently large we prove that for both and odd, and that for exactly one of and odd. We also give some upper and lower bounds for with small and . [Copyright &y& Elsevier]

For a positive integer n ⊆ N N and a set D ⊂ N, the distance graph GDn has vertex set {0; 1;...; n-1} and two vertices i and j of GDn are adjacent exactly if ∣j-i∣ ∊ D. The condition gcd(D) = 1 is necessary for a distance graph GDn being connected. Let D = {d1; d2} ⊆ N be such that d1 > d2 and gcd(d1, d2) = 1. We prove the following results. • If n is sufficiently large in terms of D, then GDn has a Hamiltonian path with endvertices 0 and n - 1. • If d1d2 is odd, n is even and sufficiently large in terms of D, then GDn has a Hamiltonian cycle. • If d1d2 is even and n is sufficiently large in terms of D, then GDn has a Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

Abstract: Motivated by the Channel Assignment Problem, we study radio -labelings of graphs. A radio -labeling of a connected graph is an assignment of non-negative integers to the vertices of such that for any two vertices and , , where is the distance between and in . In this paper, we study radio -labelings of distance graphs, i.e., graphs with the set of integers as vertex set and in which two distinct vertices are adjacent if and only if . We give some lower and upper bounds for radio -labelings of distance graphs with distance sets , and for any positive integer . [Copyright &y& Elsevier]

Abstract: In this paper we study the distance Ramsey number . The distance Ramsey number is the minimum number such that for any graph on vertices, either contains an induced -vertex subgraph isomorphic to a distance graph in or contains an induced -vertex subgraph isomorphic to the distance graph in . We obtain the upper and lower bounds on , which are similar to the bounds for the classical Ramsey number . [Copyright &y& Elsevier]

This note relates to bounds on the chromatic number Χ(Rn) of the Euclidean space, which is the minimum number of colors needed to color all the points in Rn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in Rn was introduced showing that Χ(Rn) ≥ Χ (Gn) ≥ (1 + o(1)) n²/6 . For many years, this bound has been remaining the best known bound for the chromatic numbers of some low-dimensional spaces. Here we prove that Χ(Gn) ~ n²/6 and find an exact formula for the chromatic number in the case of n = 2k and n = 2k - 1. [ABSTRACT FROM AUTHOR]

Abstract: The packing chromatic number of a graph is the smallest integer such that vertices of can be partitioned into disjoint classes where vertices in have pairwise distance greater than . We study the packing chromatic number of infinite distance graphs , i.e., graphs with the set of integers as vertex set and in which two distinct vertices are adjacent if and only if . In this paper we focus on distance graphs with . We improve some results of Togni who initiated the study. It is shown that for sufficiently large odd and for sufficiently large even . We also give a lower bound 12 for and tighten several gaps for with small . [Copyright &y& Elsevier]

Abstract: For a finite set with , we prove the existence of some such that the distance graph with vertex set in which two vertices and are adjacent exactly if , has a Hamiltonian path with endvertices and . This settles a conjecture posed by Penso et al. [L.D. Penso, D. Rautenbach, J.L. Szwarcfiter, Long cycles and paths in distance graphs, Discrete Math. 310 (2010) 3417–3420]. [Copyright &y& Elsevier]

Abstract: In 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers of paths. The characterizations lead to linear-time recognition algorithms of these classes of graphs. Furthermore, as a generalization of powers of cycles, powers of paths, and even of the well-known circulant graphs, we consider distance graphs. While the colorings of these graphs have been intensively studied, the recognition problem has been so far neglected. We propose polynomial-time recognition algorithms for these graphs under additional restrictions. [Copyright &y& Elsevier]

Abstract: For and , the distance graph has vertex set and edge set . Note that the important and very well-studied circulant graphs coincide with the regular distance graphs. A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set of order at least , there is a constant such that the greatest common divisor of the integers in is if and only if for every , has a component of order at least if and only if for every , has a cycle of order at least . Furthermore, we discuss some consequences and variants of this result. [ABSTRACT FROM AUTHOR]

The present paper is devoted to the study of the properties of distance graphs in Euclidean space. We prove, in particular, the existence of distance graphs with chromatic number of exponentially large dimension and without cliques of dimension 6. In addition, under a given constraint on the cardinality of the maximal clique, we search for distance graphs with extremal large values of the chromatic number. The resulting estimates are best possible within the framework of the proposed method, which combines probabilistic techniques with the linear-algebraic approach. [ABSTRACT FROM AUTHOR]

We present a model of the establishment and maintenance of communication between mobile agents. We assume that the agents move through a fixed environment modeled by a motion graph and are able to communicate if they are within distance at most d of each other. As the agents move randomly, we analyze the evolution in time of the connectivity between a set of w agents, asymptotically for a large number N of vertices, when w also grows large. The particular topologies of the environment we study here are the cycle and the toroidal grid. [ABSTRACT FROM AUTHOR]

Abstract: Chatrand et al. [Graph similarity and distance in graphs, Aequationes Math. 55 (1998) 129–145] have recently conjectured that all bipartite graphs are distance graphs. Here we show that all graphs of a large subclass of bipartite graphs, i.e. partial cubes, are distance graphs. [Copyright &y& Elsevier]

For a set D &sub: ℤn, the distance graph Pn(D) has ℤn as its vertex set and the edges are between vertices i and j with |i - j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D. [ABSTRACT FROM AUTHOR]

The article presents a mathematical analysis of chromatic numbers of 3-dimensional distance graphs containing no tetrahedra. It is noted that finding the so-called chromatic number x of the space for a given set of forbidden distances is a classical problem about distance graphs. Meanwhile, the Moser spindle, a graph consisting of two pairs of equilateral triangles, was described.

The article focuses on the study of two classical problems on the border between combinatorics and combinatorial geometry. The problems are consisted of computing the Ramsey numbers and computing the chromatic numbers of distance graphs. A discussion of the problems and a few words to each of the problems are presented.

A group G is called a CI-group provided that the existence of some automorphism σ ∈ Aut( G) such that σ( A) = B follows from an isomorphism Cay( G, A) ≅ = Cay ( G, B) between Cayley graphs, where A and B are two systems of generators for G. We prove that every finitely generated abelian group is a CI-group. [ABSTRACT FROM AUTHOR]

Abstract: Let be the set of real numbers and be a subset of the positive real numbers. The distance graph is a graph with the vertex set and two vertices and are adjacent if and only if . In this work, the vertex arboricity (i.e., the minimum number of subsets into which the vertex set can be partitioned so that each subset induces an acyclic subgraph) of is determined for being an interval between 1 and . [Copyright &y& Elsevier]

Abstract: A distance graph is a graph with the set of all points of the real line as vertex set and two vertices are adjacent if and only if where the distance set is a subset of the positive real numbers. Here, the vertex linear arboricity of is determined when D is an interval between 1 and . In particular, the vertex linear arboricity of integer distance graphs is discussed, too. [Copyright &y& Elsevier]

Abstract: Let be a set of positive integers. The distance graph with distance set is the graph with vertex set in which two vertices are adjacent if and only if . The fractional chromatic number, the chromatic number, and the circular chromatic number of for various 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 , where , , and are natural numbers with . In particular, we completely determine the chromatic number of for arbitrary , and . [Copyright &y& Elsevier]

Abstract: Given a set D of positive integers, the distance graph has vertices all integers Z, and two vertices j and in Z are adjacent if and only if . This paper determines the circular chromatic numbers of some distance graphs. [Copyright &y& Elsevier]

Suppose m,k,s are positive integers with m>sk. Let Dm,k,s denote the set {1,2,…,m}&z.drule;{k,2k,…,sk}. The distance graph G(Z,Dm,k,s) has as vertex set all integers Z and edges connecting i and j whenever |i−j|∈Dm,k,s. This paper determines the circular chromatic number of all the distance graphs G(Z,Dm,k,s). [Copyright &y& Elsevier]

Let D be a subset of the set P of prime numbers not containing any twin primes. Kemnitz and Kolberg raised the following question. For any given natural number n, are there only finitely many such minimal sets D, of the size n, such that the induced prime distance graph has chromatic number 4? In this paper, a conditional answer to this question based on a well-known conjecture from the prime number theory is given. [Copyright &y& Elsevier]