×

zbMATH — the first resource for mathematics

Clique, chromatic, and Lovász numbers of certain circulant graphs. (English) Zbl 1152.05352
Liberti, Leo (ed.) et al., Workshop on graphs and combinatorial optimization. Papers from the workshop, Como, Italy, May 31, 2004. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 17, 63-67 (2004).
Summary: We first study some properties of circulant graphs of degree four. In particular, we determine their clique and chromatic numbers and address issues related to their Lovász theta function. We also consider generalizations of circulant graphs, called generalized circulants, that possess certain interesting properties, such as high connectivity and comparatively small clique number. Classes of generalized circulants may have an arbitrarily large gap between the clique and the chromatic number.
For the entire collection see [Zbl 1109.05009].

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
Software:
SDPpack
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alizadeh, F., SDPPACK User’s guide
[2] Beivide, R.; Herrada, E.; Balcázar, J.L.; Arruabarrena, A., Optimal distance networks of low degree for parallel computers, IEEE trans. on computers, C-30, 10, 1109-1124, (1991) · Zbl 1395.68024
[3] Bermond, J.-C.; Comellas, F.; Hsu, D.F., Distributed loop computer networks: A survey, J. of parallel and distributed computing, 24, 2-10, (1995)
[4] Bouknight, W.J.; Denenberg, S.A.; McIntyre, D.E.; Randall, J.M.; Samel, A.H.; Slotnick, D.L., The illiac IV system, Proc. IEEE, 60, 4, 369-378, (1972)
[5] Brimkov, V.E.; Codenotti, B.; Crespi, V.; Leoncini, M., On the lovász number of certain circulant graphs, (), 291-305 · Zbl 0955.05097
[6] Dorst, L.; Duin, R.P.W., Spirograph theory: a framework for calculations on digitized straight lines, IEEE trans. pattern analysis and machine intelligence, 6, 632-639, (1984) · Zbl 0545.68098
[7] Edwards, C.S.; Elphik, C.H., Lower bounds for the clique and the chromatic numbers of a graph, Discrete applied mathematics, 5, 51-64, (1983) · Zbl 0535.05029
[8] Feige U., Randomized graph products, chromatic numbers, and the Lovász θ-function, Proc of the 27th STOC (1995) 635-640 · Zbl 1058.94517
[9] Huber, K., Codes over tori, IEEE trans. on information theory, 43, 2, 740-744, (1997) · Zbl 0870.94048
[10] Knuth, D.E., The sandwich theorem, Electronic J. combinatorics, 1, 1-48, (1994)
[11] Lovász, L., On the Shannon capacity of a graph, IEEE trans. on inf. theory, 25, 1-7, (1979) · Zbl 0395.94021
[12] Shannon, C.E., The zero-error capacity of a noisy channel, IRE trans. inform. theory, IT-2, 8-19, (1956)
[13] Wilkov, R.S., Analysis and design of reliable computer networks, IEEE trans. on communications, 20, 660-678, (1972)
[14] Wong, C.K.; Coppersmith, D., A combinatorial problem related to multimodule memory organization, Journal of the ACM, 21, 3, 392-402, (1974) · Zbl 0353.68039
[15] Yang, Y.; Funashashi, A.; Jouraku, A.; Nishi, H.; Amano, H.; Sueyoshi, T., Recursive diagonal torus: an interconnection network for massively parallel computers, IEEE trans. on parallel and distributed systems, 12, 7, 701-715, (2001)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.