Algebraic graph decomposition theory

R. I. Tyshkevich ; P. V. Skums ; S. V. Suzdal'

Trudy Instituta matematiki, Tome 18 (2010) no. 1, pp. 99-115.

Résumé

The survey of the results of the new algebraic theory of graph decomposition ($(P,Q)$-decomposition) is presented. The examples of the effective applications of this theory to the well-known hard graph-theoretical problems are given.

Bibliographie

[1] Biggs N., Algebraic Graph Theory, Cambridge Univ. Press, 1974 | MR | Zbl

[2] Bondy A., “A graph reconstructor's manual”, Surveys in Combinatorics, London Math. Soc. Lecture Notes Series, Cambridge University Press, Cambridge, 1991, 221–252 | MR

[3] Bondy A., Hemminger R.L., “Graph reconstruction — a survey”, J. Graph Theory, 1977, no. 1, 227–268 | DOI | MR | Zbl

[4] Brandstädt A., Le V.B., Spinrad J., Graph classes: a survey, SIAM monographs on discrete mathematics and applications, SIAM, Philadelphia, 1999 | MR

[5] Cornier A., Habib M., “A new linear algorithm for modular decomposition”, Lecture Notes in Computer Science, 787, 1994, 68–84

[6] Corneil D.G., Perl Y., Stewart L.K., “A linear recognition algorithm for cographs”, SIAM J. Computing, 14:4 (1985), 926–934 | DOI | MR | Zbl

[7] Cvetkovich D.M., Spectra of Graph Theory and Applications, VEB Deutscher Verlag der Wissenschaften, Berlin, 1980; Naukova dumka, Kiev, 1984

[8] Dahlhaus E., Gustedt J., McConnell R.M., Efficient and practical modular decimposition, Preprint No 524/1996, Technische Universität Berlin

[9] Földes S., Hammer P.L., “Split graphs”, Proceedings of the 8-th South-East Conf. of Combinatorics, Graph Theory and Computing, Congressus Numerantium, 19, 1977, 311–315 | MR

[10] Giakoumakis V., Roussel F., Thuillier H., “On $P_4$–tidy graphs”, Discrete Math. and Theor. Comp. Sci., 1997, no. 1, 17–41 | MR | Zbl

[11] Giakoumakis V., Quaddoura R., Suzdal S., Tyshkevich R., Operator decomposition of graphs, Preprint LaRIA 2002-09, Laboratoire de Recherche en Informatique Amiens, Amiens, France, June 2002, 26 pp.

[12] Harary F., Palmer E.L., Graphical enumeration, Academic Press, New York–London, 1973 ; Mir, M., 1977 | MR

[13] Hell P., Nesetril J., Graphs and homomorphisms, Oxford University Press, 2004 | MR | Zbl

[14] Hoang C.T., Doctoral dissertation, Montreal, 1985

[15] Hoáng C.T., Le V.B., “$P_4$-Free Colorings and $P_4$-Bipartite Graphs”, Discrete Math. and Theoretical Comp. Science, 4 (2001), 109–122 | MR | Zbl

[16] Jamison B., Olariu S., “A unique tree representation for $P_4$-sparse graphs”, Discrete Appl. Math., 35 (1992), 115–129 | DOI | MR | Zbl

[17] Jamison B., Olariu S., “p-Components and the homogeneous decomposition of graphs”, SIAM Journal of Discrete Math., 1995, no. 8, 448–463 | DOI | MR | Zbl

[18] Jamison B., Olariu S., “$P_4$-reducible graphs, a class of tree representable graphs”, Studies in Applied Mathematics, 81 (1989), 79–87 | MR | Zbl

[19] Johnson R.H., “Properties of unique realizations — a survey”, Discrete Math., 31 (1980), 185–192 | DOI | MR | Zbl

[20] Kelly P.J., On isometric transformations, PhD thesis, University of Wisconsin, 1942

[21] Kleitman D.J., Li S.-Y., “A note on unigraphic sequences”, Stud. Appl. Math., 54:4 (1975), 283–287 | MR | Zbl

[22] Koren M., “Pairs of sequences with a unique realization by bipartite graphs”, J. Combin. Theory B, 21:3 (1976), 224–234 | DOI | MR | Zbl

[23] Koren M., “Sequences with unique realization”, J. Combin. Theory B, 21:3 (1976), 235–244 | DOI | MR | Zbl

[24] Li S.-Y., “Graphic sequences with unique realization”, J. Combin. Theory B, 19:1 (1975), 42–68 | DOI | MR | Zbl

[25] Lauri J., Scapellato R., Topics in graph isomorphisms and reconstruction, Cambridge University Press, 2003 | MR

[26] Lovász L., Plummer M.D., Matching Theory, “Akademiai Kiado”, Budapest, 1986 ; Mir, M., 1998 | MR | Zbl

[27] Mahadev N.V., Peled U.N., Threshold graphs and related topics, Annals of Discrete Math., 56, 1995 | MR | Zbl

[28] McKee T.A., McMorris F.R., Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, 1999, 205 pp. | MR | Zbl

[29] Rawlinson K.T., Entringer R.C., “Class of graphs with restricted neighborhoods”, J. Graph Theory, 3 (1979), 257–262 | DOI | MR | Zbl

[30] Skums P.V., Suzdal S.V., Tyshkevich R.I., “Operator decomposition of graphs and the reconstruction conjecture”, Discrete Mathematics, 310 (2010), 423–429 | DOI | MR | Zbl

[31] Skums P.V., Tyshkevich R.I., “Reconstruction conjecture for graphs with restrictions on 4-paths”, Discrete Analysis and Operations research, 16:4, 87–96 | MR

[32] Suzdal S., Tyshkevich R., $(P,Q)$-decomposition of graphs, Preprints aus dem Fachbereich Informatik, No 5-1999, Univ. Fachbereich Informatik, Rostock, 1999, 16 pp.

[33] Thatte, B., “Some results on the reconstruction problem. $p$-claw-free, chordal and $P_4$-reducible graphs”, J. of Graph Theory, 19:4 (1995), 549–561 | DOI | MR | Zbl

[34] Tyshkevich R.I., “Decomposition of graphical sequences and unigraphs”, Discrete Mathematics, 220 (2000), 201–238 | DOI | MR | Zbl

[35] Ulam S.M., A collection of mathematical problems, Wiley (Interscience), New York, 1960 | MR

[36] Emelichev V.A., Melnikov O.I., Sarvanov V.I., Tyshkevich R.I., Lektsii po teorii grafov, Nauka, M., 1990, 384 pp. | MR | Zbl

[37] Tyshkevich R.I., “Kanonicheskaya dekompozitsiya grafov”, Dokl. AN BSSR, 24 (1980), 677–679 | MR | Zbl

[38] Tyshkevich R.I., Chernyak A.A., “Unigrafy, 1”, Izv. AN BSSR, ser. fiz.-mat. nauk, 1978, no. 5, 5–11 | MR | Zbl

[39] Tyshkevich R.I., Chernyak A.A., “Unigrafy, 2”, Izv. AN BSSR, ser. fiz.-mat. nauk, 1979, no. 1, 5–12 | MR | Zbl

[40] Tyshkevich R.I., Chernyak A.A., “Unigrafy, 3”, Izv. AN BSSR, ser. fiz.-mat. nauk, 1979, no. 2, 5–11 | MR | Zbl

[41] Tyshkevich R.I., Suzdal S.V., “Dekompozitsiya grafov”, Izbrannye nauchnye trudy Belorusskogo gosudarstvennogo universiteta, v 7 t., v. 6, Matematika, BGU, Minsk, 2001, 482—504

[42] Tyurin V., “Rekonstruktsiya razlozhimykh grafov”, Vesti AN BSSR, ser. fiz.-mat. nauk, 1987, no. 3, 16–20 | MR | Zbl