DOI: https://doi.org/10.18523/2617-7080i2018p11-14

Побудова коспектральних графiв вiдносно узагальненої матрицi сумiжностi

Daria Grushka, Viktoriia Lebid

Анотація


Спектральна теорiя графiв використовує власнi значення матриць, асоцiйованих iз графом, для визначення структурних властивостей графа. У статтi розглянуто спектр узагальненої матрицi сумiжностi. Графи з однаковим спектром називаються коспектральними. Розглянуто побудову за допомогою GM-комутацiї коспектральних графiв, якi утворенi iз циклу парної довжини C2n та однiєї точки v, яка сполучена рiвно з половиною вершин циклу. Для таких графiв при невеликих n визначено пари коспектральних графiв.

Ключові слова


узагальнена матриця сумiжностi; коспектральнi графи; GM-комутацiя

Повний текст:

PDF

Посилання


Günthard, H. H., & Primas, H. (1956). Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen. Helv. Chim. Acta., 39, 1645–1653. https://doi.org/10.1002/hlca.19560390623

Collatz, L., & Sinogowitz, U. (1957). Spektren endlicher Grafen. Abh. Math. Sem. Univ. Hamburg, 21, 63–77.https://doi.org/10.1007/bf02941924

Cvetkovich, D. M. (1971). Graphs and their spectra. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., 354–356, 1–50.

Schwenk, A. J. (1973). Almost all trees are cospectral. In F. Harary (Ed.), New Directions in the Theory of Graphs (pp. 275–307). New York: Academic Press.

Johnson, C. R., & Newman, M. (1980). A note on cospectral graphs. J. Combin. Theory B, 28, 96–103.

Cvetković, D. M., Doob, M., & Sachs, H. (1995). Spectra of Graphs. (3rd ed.). Heidelberg: Johann Ambrosius Barth Verlag.

Godsil, C., & Mckay, B. (1976). Some computational results on the spectra of graphs. In L. R. A. Casse, & W. D. Wallis (Eds.), Combinatorial Mathematics IV (pp. 73–92). Berlin: Springer-Verlag volume 560. https://doi.org/10.1007/bfb0097370

van Dam, E. R., & Haemers, W. H. (2003). Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373, 241–272. https://doi.org/10.1016/s0024-3795(03)00483-x




Bookmark and Share


Copyright (c) 2018 Daria Grushka, Viktoriia Lebid

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.