×

On the independence ratio of distance graphs. (English) Zbl 1343.05055

Summary: 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 \(G\) is the maximum density of an independent set in \(G\). K.-W. Lih et al. [SIAM J. Discrete Math. 12, No. 4, 491–499 (1999; Zbl 0935.05042)] 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 and determine asymptotic values for others.

MSC:

05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 0935.05042

Software:

Cliquer
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A., Maximal cliques in the Paley graph of square order, J. Statist. Plann. Inference, 56, 1, 33-38 (1996) · Zbl 0876.05093
[2] Barahas, J.; Serra, O., Distance graphs with maximum chromatic number, Discrete Math., 308, 1355-1365 (2008) · Zbl 1136.05018
[3] Bašić, M.; Ilić, A., On the clique number of integral circulant graphs, Appl. Math. Lett., 22, 9, 1409-1411 (2009) · Zbl 1173.05346
[4] Blokhuis, A., On subsets of GF \((q^2)\) with square differences, Indag. Math. (Proc.), 87, 4, 369-372 (1984) · Zbl 0561.12009
[5] Brimkov, V. E.; Codenotti, B.; Crespi, V.; Leoncini, M., On the Lovász number of certain circulant graphs, Lecture Notes in Comput. Sci., 1767, 291-305 (2000), CIAC 2000 · Zbl 0955.05097
[6] Broer, I.; Döman, D.; Ridley, J. N., The clique numbers and chromatic numbers of certain Paley graphs, Quaest. Math., 11, 1, 91-93 (1988) · Zbl 0634.05030
[7] Brown, J.; Hoshino, R., Proof of a conjecture on fractional Ramsey numbers, J. Graph Theory, 63, 2, 164-178 (2010) · Zbl 1216.05083
[8] Chang, G. H.; Huang, L.; Zhu, X., Circular chromatic numbers and fractional chromatic numbers of distance graphs, European J. Combin., 19, 423-431 (1998) · Zbl 0905.05032
[9] Chang, G. J.; Liu, D. D.-F.; Zhu, X., Distance graphs and \(T\)-coloring, J. Combin. Theory Ser. B, 75, 259-269 (1999) · Zbl 0930.05037
[10] Chen, J.-J.; Chang, G. J.; Huang, K.-C., Integral distance graphs, J. Graph Theory, 25, 287-294 (1997) · Zbl 0878.05028
[11] Codenotti, B.; Gerace, I.; Vigna, S., Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra Appl., 285, 123-142 (1998) · Zbl 0931.05050
[12] Cohen, S. D., Clique numbers of Paley graphs, Quaest. Math., 11, 2, 225-231 (1988) · Zbl 0691.05051
[13] Collins, K. L., Circulants and sequences, SIAM J. Discrete Math., 11, 330-339 (1998) · Zbl 0920.05037
[14] Deuber, W. A.; Zhu, X., The chromatic numbers of distance graphs, Discrete Math., 165, 194-204 (1997) · Zbl 0879.05027
[15] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Colouring the real line, J. Combin. Theory Ser. B, 39, 86-100 (1985) · Zbl 0549.05029
[16] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Coloring prime distance graphs, Graphs Combin., 32, 17-32 (1990) · Zbl 0698.05033
[17] Ekstein, J.; Holub, P.; Lidický, B., Packing chromatic number of distance graphs, Discrete Appl. Math., 160, 518-524 (2012) · Zbl 1239.05050
[18] Ekstein, J.; Holub, P.; Togni, O., The packing coloring of distance graphs \(D(k, t)\), Discrete Appl. Math., 167, 100-106 (2014) · Zbl 1284.05213
[19] Gao, G.; Zhu, X., Star extremal graphs and the lexicographic product, Discrete Math., 165-166, 147-156 (1996) · Zbl 0852.05046
[20] Green, B., Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica, 25, 3, 307-326 (2005) · Zbl 1110.11009
[21] Hartke, S. G.; Stolee, D., Uniquely \(K_r\)-Saturated Graphs, Electron. J. Combin., 19, 4, R6 (2012), 40 pp. · Zbl 1266.05057
[22] Heuberger, C., On planarity and colorability of circulant graphs, Discrete Math., 268, 153-169 (2003) · Zbl 1028.05024
[23] Hoshino, R., Independence polynomials of circulant graphs (2007), Dalhousie University, (Ph.D. Thesis)
[24] Ilić, A., The energy of unitary Cayley graphs, Linear Algebra Appl., 431, 1881-1889 (2009) · Zbl 1175.05086
[25] Ilić, A.; Bašić, M., On the chromatic number of integral circulant graphs, Comput. Math. Appl., 60, 144-150 (2010) · Zbl 1198.05055
[26] Katznelson, Y., Chromatic numbers of Cayley graphs on \(Z\) and recurrence, Combinatorica, 21, 2, 211-219 (2001) · Zbl 0981.05038
[27] Kemnitz, A.; Kolberg, H., Coloring of integer distance graphs, Discrete Math., 191, 113-123 (1998) · Zbl 0956.05044
[28] Klotz, W.; Sander, T., Some properties of unitary Cayley graphs, Electron. J. Combin., 14, #R45 (2007) · Zbl 1121.05059
[29] Lam, P. C.B.; Lin, W., Coloring of distance graphs with intervals as distance sets, European J. Combin., 26, 1216-1229 (2005) · Zbl 1082.05038
[30] Li, Y.; Shen, J., Bounds for Ramsey numbers of complete graphs dropping an edge, European J. Combin., 29, 88-94 (2008) · Zbl 1131.05059
[31] Lih, K.-W.; Liu, D. D.-F.; Zhu, X., Star extremal circulant graphs, SIAM J. Discrete Math., 12, 491-499 (1999) · Zbl 0935.05042
[32] Liu, D. D.-F., From rainbow to the lonely runner: A survey on coloring parameters of distance graphs, Taiwanese J. Math., 12, 851-871 (2008) · Zbl 1168.05310
[33] Liu, D. D.-F.; Sutedja, A., Chromatic number of distance graphs generated by the sets \(\{2, 3, x, y \}\), J. Comb. Optim., 25, 680-693 (2013) · Zbl 1273.90230
[34] Liu, D. D.-F.; Zhu, X., Distance graphs with missing multiples in the distance sets, J. Graph Theory, 30, 245-259 (1999) · Zbl 0915.05056
[35] Liu, D. D.-F.; Zhu, X., Fractional chromatic number and circular chromatic number for distance graphs with large clique size, J. Graph Theory, 47, 2, 129-146 (2004) · Zbl 1055.05059
[36] Maistrelli, E.; Penman, D. B., Some colouring problems for Paley graphs, Discrete Math., 306, 99-106 (2006) · Zbl 1085.05031
[37] Miklavič, Š.; Potočnik, P., Distance-regular circulants, European J. Combin., 24, 777-784 (2003) · Zbl 1026.05107
[38] Niskanen, S.; Östergård, P. R.J., Cliquer user’s guide, version 1.0. Technical Report T48 (2003), Communications Laboratory, Helsinki University of Technology: Communications Laboratory, Helsinki University of Technology Espoo, Finland
[39] Paley, R. E.A. C., On orthogonal matrices, J. Math. Phys., 12, 311-320 (1933) · JFM 59.0114.04
[40] Ruzsa, I. Z.; Tuza, Zs.; Voigt, M., Distance graphs with finite chromatic number, J. Combin. Theory Ser. B, 85, 181-187 (2002) · Zbl 1027.05036
[41] Togni, O., On packing colorings of distance graphs, Discrete Appl. Math., 167, 280-289 (2014) · Zbl 1284.05109
[42] Zhu, X., Circular chromatic number of distance graphs with distance sets of cardinality 3, J. Graph Theory, 41, 195-207 (2002) · Zbl 1012.05071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.