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

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сть.

The 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.