članak: 1 od 1  
Publikacija Elektrotehničkog fakulteta - serija: matematika
2002, br. 13, str. 42-65
jezik rada: engleski
neklasifikovan
doi:10.2298/PETF0213042B

A survey on integral graphs
(naslov ne postoji na srpskom)
aTechnical University of Poznan, Poland
bUniverzitet u Beogradu, Elektrotehnički fakultet
cUniverzitet u Nišu, Prirodno-matematički fakultet

e-adresa: balinska@man.poznan.pl

Sažetak

(ne postoji na srpskom)
A graph whose spectrum consists entirely of integers is called an integral graph. We present a survey of results on integral graphs and on the corresponding proof techniques.

Ključne reči

Reference

Balinska, K., Kupczyk, M., Zwierzynski, K. (1997) Methods of generating integral graphs. Poznan: Technical University, Computer Science Center Report br. 457, 1-68
Balinska, K.T., Kupczyk, M., Simić, S.K., Zwierzynski, K.T. (2001) On generating all integral graphs on 12 vertices. Poznan: Technical University, Computer Science Center Report br. 482
Balinska, K.T., Kupczyk, M., Simić, S.K., Zwierzynski, K.T. (1999/2000) On generating all integral graphs on 11 vertices. Poznan: Technical University, Computer Science Center Report br. 469
Balinska, K.T., Simić, S.K., Zwierzinsky, K.T. (2004) Which non-regular bipartite integral graphs with maximum degree four do not have +/- 1 as eigenvalues?
Balinska, K., Cvetković, D., Lepović, M., Simić, S. (1999) There are exactly $150$ connected integral graphs up to $10$ vertices. Publikacija Elektrotehničkog fakulteta - serija: matematika, 10, 95-105
Balinska, K.T., Simić, S.K. (2001) The nonregular, bipartite, integral graphs with maximum degree 4. Part I: basic properties
Baliriska, K.T., Simić, S.K. (2001) Some remarks on integral graphs with maximum degree four. Journal of Mathematics, Novi Sad, vol. 31, br. 1, str. 19-25
Bussemaker, F.C., Cvetković, D.M., Seidel, J.J. (1976) Graphs related to exceptional root systems. Eindhoven: Technological University, T. H. -Report 76 -WSK- 05
Bussemaker, F.C., Cvetković, D.M. (1976) There are exactly 13 connected, cubic, integral graphs. Publ. Elektrotehničkog fakulteta - serija: matematika i fizika, 576, 43-48
Bussemaker, F.C., Cobeljić, S.C., Cvetković, D., Seidel, J.J. (1976) Computer investigation of cubic graphs. Eindhoven: Technological University, T.H.-Report 76-WSK-01 1-66
Bussemaker, F.C., Cobeljić, S., Cvetković, D.M., Seidel, J.J. (1977) Cubic graphs on $\leq 14$ vertices. Journal of Combinatorial Theory Series B, 23, 3, 234-235
Bussemaker, F.C., Mathon, R.A., Seidel, J.J. (1979) Tables of two-graphs. Eindhoven: Technological University, T. H. -Report 79-WSK-05
Cao, Z.F. (1988) On the integral trees of diameter R when 3 < R < 6. Journal of Heilongjiang Univ., 2. 1-3
Cao, Z.F. (1991) Some new classes of integral trees with diameter 5 or 6. Journal of Systems Sci. and Math. Sci., 11: 1 20-26.(Chinese, English summary)
Cvetković, D.M. (1975) Cubic integral graphs. Publ. Elektrotehničkog fakulteta - serija: matematika i fizika, 541, 107-541, (1975), 107--113
Cvetković, D.M. (1975) Spectra of graphs formed by some unary operations. Publications de l'Institut mathematique, 19(33), 37-41
Cvetković, D.M. (1989) Some graph invariants based on the eigenvectors of the adjacency matrix. u: R.Tošić D.Acketa, V.Petrović, R. Doroslovački (ur.) Proc. 8th Yugoslav Sem. on Graph Theory, 1987, Novi Sad: Institute of Mathematics
Cvetković, D.M., Doob, M. (1985) Developments in the theory of graph spectra. Linear and Multilinear Algebra, 18, 2, 153-181
Cvetković, D.M., Doob, M., Gutman, I.A., Torgašev, A. (1988) Recent results in the theory of graph spectra. Annals of Discrete Mathematics, 36
Cvetković, D.M., Doob, M., Sachs, H. (1980) Spectra of graphs: Theory and application. New York: Academic Press
Cvetković, D.M., Doob, M., Simić, S. (1980) Some results on generalized line graphs. C. R. Math. Rep. Acad. Sci. Canada, 2, 3, 147-150
Cvetković, D.M., Doob, M., Simić, S. (1981) Generalized line graphs. Journal of Graph Theory, 5, 4, 385-399
Cvetković, D.M., Gutman, I., Trinajstić, N. (1974) Conjugated molecules having integral graph spectra. Chemical Physics Letters, 29 65-68
Cvetković, D.M., Petrić, M. (1983) Connectedness of the noncomplete extended p-sum of graphs. Zbornik radova Prirodno-matematičkog fakulteta u Novom Sadu: Serija Matematika, 13 345-352
Cvetković, D.M., Petrić, M. (1984) A table of connected graphs on six vertices. Discrete Mathematics, 50, 1, 37-49
Cvetković, D.M., Rowlinson, P. (1988) Further properties of graph angles. Scienta (Valparaiso), 1 41-51
Cvetković, D.M., Rowlinson, P., Simić, S.K. (1997) Eigenspaces of graphs. u: Encyclopedia of Mathematics and its Applications, Cambridge, itd: Cambridge University Press / CUP, vol. 66
Cvetković, D.M., Simić, S.K., Stevanović, D. (1998) 4-regular integral graphs. Publikacija Elektrotehničkog fakulteta - serija: matematika, 9, 89-102
Doob, M. (1973) An interrelation between line graphs, eigenvalues, and matroids. Journal of Combinatorial Theory Series B, 15, 40-50
Esser, F., Harary, F. (1980) Digraphs with real and Gaussian spectra. Discrete Applied Mathematics, 2, 2, 113-124
Grone, R., Merris, R. (1994) The Laplacian spectrum of a graph. II. SIAM Journal on Discrete Mathematics, 7, 2, 221-229
Hansen, P., Melot, H., Stevanović, D.P. (2002) Integral complete split graphs. Publikacija Elektrotehničkog fakulteta - serija: matematika, br. 13, str. 89-95
Harary, F., Schwenk, A.J. (1974) Which graphs have integral spectra?. u: R.Bari and F.Harary (ur.) Graphs and Combinatorics (Lecture Notes in Mathematics, 406), Berlin, itd: Springer Verlag, 45-51
Harary, F. (1969) Graph theory. Reading, MA, itd: Addison-Wesley
Hic, P. (1992) A construction of integral graphs VI. u: Vedeck'a konferencia, EF TU Kosice, 34-39
Hic, P. (1997) On balanced integral trees of diameter. u: 6 CO-MAT-TECH 97, 5. Vedeck'a konferencia s medzin'arodnou 'ucastou, Trnava, 125-129
Hic, P., Nedela, R. (1996) A note on zeroes of the characteristic polynomial of balanced trees. Acta Unic. M. Bellii, Sr. Math., br. 3 31-35
Hic, P., Nedela, R. (1998) Balanced integral trees. Math. Slovaca, 48, 5, 429-445
Hic, P., Nedela, R., PavlikovA, S. (1992) Front-divisors of trees. Acta Math. Univ. Comenianae, 61, 1, 69-84
Hic, P., PavlikovA, S. (1995) Integral bibalanced trees. u: The collection of papers of the Faculty of materials science and technology, Trnava, vol. 3, 227-233
Hic, P., Sotakova, K. (1999) Two constructions of nonsymetric strong integral graphs. Acta Fac Paed Univ Tyrnaviensis, Ser B, no 3, 107-120
Hoffman, A.J. (1963) On the polynomial of the graph. American Mathematical Monthly, 70 30-36
Kraus, L.L., Cvetković, D. (1972) Tables of simple eigenvalues of some graphs whose automorphism group has two orbits. Publ. Elektrotehničkog fakulteta - serija: matematika i fizika, 409, 89-95
Li, M.S., Yang, W.S., Wang, J. (2000) Notes on the spectra of trees with small diameters. Journal of Changsha Railway University, 18 2 84-87
Li, X.L., Wang, L. (2000) Integral trees - A survey. Chinese Journal of Engineering Math., 17 5 91-93
Li, X.L., Lin, G. (1987) On the problem of integral trees. Kexue Tongbao, 32, 11, 813-816
Liu, R. (1988) New families of trees with integral eigenvalues. Journal of Qinghai Normal Univ., 3 1-5 (Chinese, English summary)
Liu, R.Y. (1988) Integral trees of diameter. Journal of Systems Sci Math Sci, 8 4 357-360.(Chinese, English summary)
Lix, L., Lin, G. (1988) On integral trees problems. Kexue Tongbao, 33, 10, 802-806
Merris, R. (1994) Laplacian matrices of graphs: A survey. Linear Algebra and its Applications, 197/198, 143-176
Merris, R. (1995) A survey of graph Laplacians. Linear and Multilinear Algebra, 39, 2, 19-31
Merris, R. (1994) Degree maximal graphs are Laplacian integral. Linear Algebra and its Applications, 199, 381-389
Mohar, B. (1991) The Laplacian spectrum of graphs. u: Alavi Y., Chartrand G., Ollermann O.R., Schwenk A.J. (ur.) Graph theory, combinatorics, and applications, New York, itd: Wiley, str. 871-898
Petrović, M., Radosavljević, Z. (2001) Spectrally constrained graphs. Kragujevac: Faculty of Science
Radosavljević, Z., Simić, S. (1986) There are just thirteen connected nonregular nonbipartite integral graphs having maximum vertex degree four. u: Proc Sixth Yugoslav Seminar on Graph Theory, Dubrovnik, 183-187
Ren, H. (2000) On integral trees with diameter. Journal of Qinghai Normal Univ., 1, 8-11
Roitman, M. (1984) An infinite family of integral graphs. Discrete Mathematics, 52, 3, 313-315
Sachs, H. (1964) Beziehungen zwischen den in einem Graphen enthaltenen Kreisen und seinem charakteristischen Polynom. Publ. Math. Debrecen, 11, 119-134
Schwenk, A. (1974) Computing the characteristic polynomial of a graph. Lecture Notes in Mathematics, br. 406, str. 153-172
Schwenk, A. (1976) Exactly thirteen connected cubic graphs have integral spectra. u: Proceedings of the International Graph Theory Conference at Kalamazoo, May, Berlin, itd: Springer Verlag
Simić, S., Radosavljević, Z. (1987) Some computer-aided investigations in graph theory. u: Proc. Symposium on Optimization, Design Exper. and Graph Theory, Bombay, 307-313
Simić, S., Radosavljević, Z. (1995) The nonregular, nonbipartite, integral graphs with maximum degree four. J Combin. Inform. System Sci., 20, 4, 9-26
Smith, J.H. (1970) Some properties of the spectrum of a graph. u: Guy R., H.Hanani, N. Sauer, J. Schonheim (ur.) Combinatorial structures and their applications, New York, itd: Gordon and Breach Science Publishers, str. 403-406
Stevanović, D. (1999) Nonexistence of some 4-regular integral graphs. Publikacija Elektrotehničkog fakulteta - serija: matematika, 10, 81-86
Stevanović, D. (2000) Some graph compositions and integral graphs. Niš: Faculty of Sciences, Ph. D. Thesis
Stevanović, D.P. (2003) 4-regular integral graphs avoiding ±3 in the spectrum. Publikacija Elektrotehničkog fakulteta - serija: matematika, br. 14, str. 99-110
Strunkov, S.P. (1990) A theorem of Cvetkovi\'c in graph theory. Uspekhi Matematicheskikh Nauk, 45, 6, 168-146
Strunkov, S.P. (1993) Some finiteness theorems for integral non-negative matrices and graphs. Ukrainian Acad. Sci., Inst. Math., Kiev, 488-499
Strunkov, S.P. (2001) On weakly cospectral graphs. Doklady Akademii Nauk SSSR, 379, 3, 302-304
Wang, L.G., Li, X.L. (2000) Some new classes of integral trees with diameters 4 and 6. Australas. J. Combin., 21, 237-243
Wang, L.G., Li, X.L., Liu, R.Y. (1999) Integral trees with diameter 6 or 8. u: Electronic Notes in Discrete Math
Wang, L.G., Li, X.L., Yao, X.J. (2002) Integral trees with diameters 4, 6 and 8. Australas. J. Combin., 25, 29-44
Wang, L.G., Li, X.L., Zhang, S.G. (2000) Construction of integral graphs. Appl Math J Chinese Univ Ser B, 15, 3, 239-246
Wang, L.G., Li, X.L., Zhang, S.G. (2001) Some new families of integral trees with diameters 4, 6 and 8. u: Electronic Notes in Discrete Math. Vol. 8
Watanabe, M. (1979) Note on integral trees. Math. Rep. Toyama Univ., 2, 95-100
Watanabe, M., Schwenk, A.J. (1979) Integral starlike trees. Journal of the Australian Mathematical Society, 28, 120-128
Xu, D.S. (1996) A note on the integral trees with diameter 4. Journal of Qinghai Univ., 14:2 16-18
Xu, D.S. (1997) Some new classes of the integral trees with diameter 4. Journal of Hebei Univ., 17:1 12-16. (Chinese, English summary)
Yizhong, F. (2002) On spectral integral variations of graphs. Linear and Multilinear Algebra, 50, 2, 133-142
Yuan, P.Z. (1998) Integral trees of diameter 4. Journal of Systems Sci. and Math. Sci., 18:2, 177-181. (Chinese, English summary)
Zhang, D.L., Tan, S.W. (2000) On integral trees of diameter 4. Journal of Systems Sci. and Math. Sci., 20:3, 330-337
Zhang, D.L., Wei, L.Y. (1998) On the existence of integral trees of diameter 4. Journal of Guangxi Inst. of Technology, 9:4 1-5