Abstract: A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio of a distance graph is the maximum density of an independent set in . Lih, Liu, and Zhu [Star extremal circulant graphs, SIAM J. Discrete Math. 12 (1999) 491--499] showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs. We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three, determine asymptotic values for others, and present several conjectures.
Recommendations
Cites work
- scientific article; zbMATH DE number 1275588 (Why is no real title available?)
- scientific article; zbMATH DE number 1507223 (Why is no real title available?)
- scientific article; zbMATH DE number 3893303 (Why is no real title available?)
- Bounds for Ramsey numbers of complete graphs dropping an edge
- CLIQUE NUMBERS OF PALEY GRAPHS
- Chromatic number of distance graphs generated by the sets \(\{2,3,x,y\}\)
- Chromatic numbers of Cayley graphs on \(\mathbb Z\) and recurrence
- Circulants and Sequences
- Circular chromatic number of distance graphs with distance sets of cardinality 3
- Circular chromatic numbers and fractional chromatic numbers of distance graphs
- Coloring of distance graphs with intervals as distance sets
- Coloring of integer distance graphs
- Colouring prime distance graphs
- Colouring the real line
- Counting sets with small sumset, and the clique number of random Cayley graphs
- Distance graphs and \(T\)-coloring
- Distance graphs with finite chromatic number
- Distance graphs with maximum chromatic number
- Distance-regular circulants
- Fractional chromatic number and circular chromatic number for distance graphs with large clique size
- From rainbow to the lonely runner: A survey on coloring parameters of distances graphs
- Hardness results and spectral techniques for combinatorial problems on circulant graphs
- Integral distance graphs
- Maximal cliques in the Paley graph of square order
- On packing colorings of distance graphs
- On planarity and colorability of circulant graphs
- On the chromatic number of integral circulant graphs
- On the clique number of integral circulant graphs
- Packing chromatic number of distance graphs
- Proof of a conjecture on fractional Ramsey numbers
- Some colouring problems for Paley graphs
- Some properties of unitary Cayley graphs
- Star Extremal Circulant Graphs
- Star-extremal graphs and the lexicographic product
- THE CLIQUE NUMBERS AND CHROMATIC NUMBERS OF CERTAIN PALEY GRAPHS
- The chromatic numbers of distance graphs
- The energy of unitary Cayley graphs
- The packing coloring of distance graphs \(D(k,t)\)
- Uniquely \(K_r\)-saturated graphs
Cited in
(9)- Bipartite density and the independence ratio
- Domination ratio of a family of integer distance digraphs with arbitrary degree
- Sequences of integers with three missing separations
- On optimal \(M\)-sets related to Motzkin's problem
- Maximal density of integral sets with missing differences and the kappa values
- On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
- Domination ratio of integer distance digraphs
- Independence numbers of random subgraphs of a distance graph
- On the independence number of minimum distance graphs
This page was built for publication: On the independence ratio of distance graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q738864)
