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

Simple item page
dc.contributor.authorГрушка, Дар'я
dc.contributor.authorЛебідь, Вікторія
dc.date.accessioned2018-12-14T14:44:27Z
dc.date.available2018-12-14T14:44:27Z
dc.date.issued2018
dc.description.abstractСпектральна теорiя графiв використовує власнi значення матриць, асоцiйованих iз графом, для визначення структурних властивостей графа. У статтi розглянуто спектр узагальненої матрицi сумiжностi. Графи з однаковим спектром називаються коспектральними. Розглянуто побудову за допомогою GM-комутацiї коспектральних графiв, якi утворенi iз циклу парної довжини C2n та однiєї точки v, яка сполучена рiвно з половиною вершин циклу. Для таких графiв при невеликих n визначено пари коспектральних графiв.uk_UA
dc.description.abstractSpectral graph theory uses the eigenvalues of matrices associated with a graph to determine the structural properties of the graph. The spectrum of the generalized adjacency matrix is considered in the paper. Graphs with the same spectrum are called cospectral. Is every graph uniquely determined by its spectrum (DS for short)? This question goes back for about half a century, and originates from chemistry. In 1956 Gunthard and Primas raised the question in a paper that related the theory of graph spectra to Huckel’s theory. At that time it was believed that every graph is determined by the spectrum, until in 1957 Collatz and Sinogowitz presented a pair of cospectral trees. In 1967 Schwenk proved that for almost all trees there is another tree with the same spectrum. Such a statement is neither proved nor refuted for the class of graphs in general. Till now, computational experiments were done on the set of all graphs on up to 12 vertices by Haemers. Computer enumerations for small n show that up to 10 vertices the fraction of graphs that are DS decreases, but for n = 11 and n = 12 it increases again. We consider the construction of the cospectral graphs called GM-switching for graph G taking the cycle C2n and adjoining a vertex v adjacent to half the vertices of C2n. For these graphs we determine the pairs of cospectral nonisomorphic graphs for small n. It is an operation on graphs that leaves the spectrum of the generalized adjacency matrix invariant. It turns out that for the enumerated cases a large part of all cospectral graphs comes from GM switching, and that the fraction of graphs on n vertices with a cospectral mate starts to decrease at some value of n < 11 (depending on the matrix). Since the fraction of cospectral graphs on n vertices constructible by GM switching tends to 0 if n → ∞, the present data give some indication that possibly almost no graph has a cospectral mate. Haemers and Spence derived asymptotic lower bounds for the number of graphs with a cospectral mate from GM switching.en_US
dc.identifier.citationГрушка Д. С. Побудова коспектральних графів відносно узагальненої матриці суміжності / Грушка Д. С., Лебідь В. О. // Могилянський математичний журнал : науковий журнал. - 2018. - Т. 1. - С. 11-14.uk_UA
dc.identifier.issn2617-7080
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/14918
dc.identifier.urihttps://doi.org/10.18523/2617-7080i2018p11-14
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журнал : науковий журнал. - 2018. - Т. 1uk_UA
dc.statusfirst publisheduk_UA
dc.subjectузагальнена матриця сумiжностiuk_UA
dc.subjectкоспектральнi графиuk_UA
dc.subjectGM-комутацiяuk_UA
dc.subjectстаттяuk_UA
dc.subjectgeneralized adjacency matrixen_US
dc.subjectcospectral graphsen_US
dc.subjectGM-switchingen_US
dc.titleПобудова коспектральних графів відносно узагальненої матриці суміжностіuk_UA
dc.title.alternativeConstruction of cospectral graphs with respect to the generalized adjacency matrixen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Hrushka_Pobudova_kospektralnykh_hrafiv_vidnosno_uzahalnenoi.pdf
Size:
151.6 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 1
Кафедра математики