Антиподальні графи діаметра 4

Simple item page
dc.contributor.authorПрончук, Людмила
dc.date.accessioned2018-12-13T15:23:31Z
dc.date.available2018-12-13T15:23:31Z
dc.date.issued2018
dc.description.abstractМетричний простiр (X, d) називається антиподальним, якщо для довiльної точки x iснує таке y, що для довiльної точки z множини X виконується рiвнiсть d(x, z) + d(z, y) = d(x, y). Вiдомими конструкцiями антиподальних графiв є графи Хемiнга, графи Джонсона, графи вечiрки (Coctail-party графи). У статтi [1] було побудовано конструкцiю антиподальних графiв дiаметра 3. Використовуючи iдею конструкцiї Стевановича P(G) з [1], побудовано конструкцiю для напiвканонiчних графiв на множинi з чотирьох вершин F(G), за допомогою якої можна побудувати антиподальнi графи дiаметра 4. Оскiльки iснує всього два напiвканонiчних графи на множинi з чотирьох вершин, побудовано два антиподальних графи дiаметра 4. Для кожного з них доведено антиподальнiсть.uk_UA
dc.description.abstractThe metric space (X, d) is called antipodal if for an arbitrary point x exists the one point y such that for an arbitrary point z of the set X the equality d(z, x) + d(z, y) = d(x, y) holds. In other words, the metric space (X, d) is called antipodal if for an arbitrary x there exists an antipode. For any connected undirected finite graph G we define the associated graph distance. The distance between two vertices v1 and v2 in G equals to the length of the shortest path between v1 and v2. A connected undirected finite graph G is called antipodal if its associated graph metric is antipodal. Hamming’s graphs, Johnson’s graphs and Coctail-party graphs are well-known constructions of antipodal graphs. In particular, the antipodal graphs of diameter 2 only are Cocktail-party graphs. Cocktail-party graph is the graph consisting of two rows of paired vertices in which all vertices but the paired ones are connected with a graph edge. In the article [1] was characterized antipodal graphs of diameter 3. In this paper was showed that almost every graph is an induced subgraph of some antipodal graph P(G) of diameter 3. The construction P(G) used connected undirected finite semi-canonical graphs. Using an idea by Dragan Stevanovic from [1], we introduce the construction of graphs which allows to construct antipodal graphs of diameter 4. The basis of this construction is using semi-canonical graphs on a set of four vertices. A graph G is called semi-canonical if for any vertex v of this graph there is at least one vertex u of graph G, such that v and u are not connected by edge. There are only two semi-canonical graphs in a set of four vertices that are C4 and L4 the cycle and the path on 4 vertices correspondingly. So, we construct two antipodal graphs of diameter 4. We prove the antipodal of both of these graphs.en_US
dc.identifier.citationПрончук Л. С. Антиподальні графи діаметра 4 / Прончук Л. С. // Могилянський математичний журнал : науковий журнал. - 2018. - Т. 1. - С. 34-37.uk_UA
dc.identifier.issn2617-7080
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/14913
dc.identifier.urihttps://doi.org/10.18523/2617-7080i2018p34-37
dc.language.isoukuk_UA
dc.relation.sourceМогилянський математичний журнал : науковий журнал. - 2018. - Т. 1uk_UA
dc.statusfirst publisheduk_UA
dc.subjectантиподальний графuk_UA
dc.subjectдiаметр графаuk_UA
dc.subjectграф вечiркиuk_UA
dc.subjectстаттяuk_UA
dc.subjectantipodal graphsen_US
dc.subjectdiameter of graphen_US
dc.subjectCoctail-party graphen_US
dc.titleАнтиподальні графи діаметра 4uk_UA
dc.title.alternativeAntipodal graphs of diameter 4en_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Pronchuk_Antypodalni_hrafy_diametra.pdf
Size:
277.56 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