×

Powers of cycles, powers of paths, and distance graphs. (English) Zbl 1213.05148

Summary: M. C. Golumbic and P. L. Hammer [J. Algorithms 9, No.3, 314–320 (1988; Zbl 0651.68083)] 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.

MSC:

05C38 Paths and cycles
05C12 Distance in graphs

Citations:

Zbl 0651.68083
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bermond, J.-C.; Comellas, F.; Hsu, D. F., Distributed loop computer networks: a survey, J. Parallel Distrib. Comput., 24, 2-10 (1985)
[2] Bogart, K. P.; West, D. B., A short proof that proper = unit, Discrete Math., 201, 21-23 (1999) · Zbl 0932.05065
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1134.05001
[4] Chang, G. J.; Huang, L.; Zhu, X., Circular chromatic numbers and fractional chromatic numbers of distance graphs, European J. Combin., 19, 423-431 (1998) · Zbl 0905.05032
[5] Corneil, D. G., A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, Discrete Appl. Math., 138, 371-379 (2004) · Zbl 1042.05067
[6] Corneil, D. G.; Kim, H.; Natarajan, S.; Olariu, S.; Sprague, A. P., Simple linear time recognition of unit interval graphs, Inform. Process. Lett., 55, 99-104 (1995) · Zbl 0875.68690
[7] Deng, X.; Hell, P.; Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput., 25, 390-403 (1996) · Zbl 0858.05094
[8] Deuber, W.; Zhu, X., The chromatic number of distance graphs, Discrete Math., 165-166, 195-204 (1997) · Zbl 0879.05027
[9] Effantin, B.; Kheddouci, H., The \(b\)-chromatic number of some power graphs, Discrete Math. Theor. Comput. Sci., 6, 45-54 (2003) · Zbl 1012.05068
[10] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Coloring the real line, J. Combin. Theory Ser. B, 39, 86-100 (1985) · Zbl 0549.05029
[11] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Colouring prime distance graphs, Graphs Combin., 6, 17-32 (1990) · Zbl 0698.05033
[12] Evdokimov, S. A.; Ponomarenko, I. N., Circulant graphs: recognizing and isomorphism testing in polynomial time, St. Petersburg Math. J., 15, 813-835 (2004), (English. Russian original). Translation from Algebra Anal. 15 (2003) 1-34 · Zbl 1061.05045
[13] Gardi, F., The Roberts characterization of proper and unit interval graphs, Discrete Math., 307, 2906-2908 (2007) · Zbl 1126.05084
[14] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York, NY · Zbl 0541.05054
[15] Golumbic, M. C.; Hammer, P. L., Stability in circular arc graphs, J. Algorithms, 9, 314-320 (1988) · Zbl 0651.68083
[16] Hell, P.; Huang, J., Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs, SIAM J. Discrete Math., 18, 554-570 (2005) · Zbl 1069.05056
[17] Herrera de Figueiredo, C. M.; Meidanis, J.; Picinin de Mello, C., A linear-time algorithm for proper interval graph recognition, Inform. Process. Lett., 56, 179-184 (1995) · Zbl 0875.68696
[18] Kaplan, H.; Nussbaum, Y., Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 4271 (2006), Springer: Springer Berlin), 289-300 · Zbl 1167.05333
[19] Kemnitz, A.; Kolberg, H., Coloring of integer distance graphs, Discrete Math., 191, 113-123 (1998) · Zbl 0956.05044
[20] Kemnitz, A.; Marangio, M., Colorings and list colorings of integer distance graphs, Congr. Numer., 151, 75-84 (2001) · Zbl 0989.05039
[21] McConnell, R. M., Linear-time recognition of circular-arc graphs, Algorithmica, 37, 93-147 (2003) · Zbl 1060.68088
[22] Muzychuk, M., A solution of the isomorphism problem for circulant graphs, Proc. Lond. Math. Soc., Ser. III, 88, 1-41 (2004) · Zbl 1045.05052
[23] Muzychuk, M.; Tinhofer, G., Recognizing circulant graphs of prime order in polynomial time, J. Combin., 5, 347-374 (1998)
[24] Muzychuk, M.; Tinhofer, G., Recognizing circulant graphs in polynomial time: an application of association schemes, Electron. J. Combin., 8, #R26 (2001)
[25] Ponomarenko, I., Polynomial-time algorithms for recognizing and isomorphism testing of cyclic tournaments, Acta Appl. Math., 29, 139-160 (1992) · Zbl 0778.05077
[26] Roberts, F. S., Indifference graphs, (Proof Techniques in Graph Theory, Proc. Second Ann Arbor Graph Theory Conf.. Proof Techniques in Graph Theory, Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968 (1969), Academic Press: Academic Press New York), 139-146 · Zbl 0193.24205
[27] Voigt, M., Colouring of distance graphs, Ars Combin., 52, 3-12 (1999) · Zbl 0977.05047
[28] Voigt, M.; Walther, H., Chromatic number of prime distance graphs, Discrete Appl. Math., 51, 197-209 (1994) · Zbl 0808.05051
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.