РЕЦЕНЗИЯ

ON THE PRESERVATION OF THE WIENER INDEX OF CUBIC GRAPHS UPON VERTEX REMOVAL

A.A. DOBRYNIN

В работе решена представленная в работе [11] проблема существования графов, у которых индекс Уинера не изменяется при удалении некоторой вершины. А именно, представлена бесконечная серия (на самом деле, две серии) таких графов. Результат относится к классу фактов, которые трудно установить, но легко проверить. После того, как конструкция предъявлена, доказательство состоит в прямой проверке, которая, однако, может быть технически непростой. В работе представлена формула для индекса Уинера двухпараметрического класса графов, а также формула для индекса Уинера этих графов после удаления конкретной вершины. В частности, при определенном соотношении параметров, две формулы дают одно и то же значение. Представлено подробное аналитическое доказательство. Следует отметить, что результат также получается и вычислительным образом, достаточно установить, что индекс Уинера кубически зависит от параметров, и посчитать несколько первых значений. Для проверки я повторил вычисления (sage программа приведена ниже), все значения в таблицах совпали, кроме одного (очевидная опечатка). Работа интересная и актуальная, рекомендую опубликование с учетом следующих двух замечаний:

1. Proposition 1 в разделе 2 приводится без комментариев и доказательства, что вводит читателя во временное замешательство, до выяснения обстоятельств. Предлагаю добавить вводное предложение типа
"Ключевое утверждение, которое будет доказано в следующем разделе и из которого напрямую вытекает основной результат (следствие 1), следующее:"

2. Таблица 2: 9048542 должно быть 904854

def ladder(i0,n):
    return [[i0+2*i,i0+2*i+1] \
            for i in range(n)]+[[i0+i,i0+i+2] \
            for i in range(2*n-2)]

def Dgraph(k,s,kk=0):
    if not kk: kk = k
    E = ladder(2*s,k)+ladder(0,s)+ladder(2*s+2*k,kk) \
        + [[-1,0],[-1,2*s],[-1,2*s+1], \
           [-2,1], [-2,2*s+2*k-1],[-2,2*s+2*k-2]] \
        + [[-3,2*s-2],[-3,2*s+2*k],[-3,2*s+2*k+1], \
           [-4,2*s-1],[-4,2*s+2*k+2*kk-1], \
           [-4,2*s+2*k+2*kk-2]]
    return Graph(E)

def Wi(k,s=0):
    if not s:
        if (k//2)*2==k: s = (k*k-4*k-4)/2
        else: s = (k*k-4*k-5)/2
    G=Dgraph(k,s); GG = G.copy(); GG.delete_vertex(s)
    print("k,s,order,W,W,W-,W-:",k,s,G.order(), \
           G.wiener_index(), 
           3*k*k*k + k*k*(12*s+39)/2 + k*(4*s*s+20*s+19) \
           + s*(2*s*s+15*s+34)/3 + 8, \
           GG.wiener_index(), \
           3*k*k*k + k*k*(12*s+41)/2 + k*(4*s*s+20*s+15) \
           + s*(2*s*s+15*s+28)/3 + 4 )

for k in range(6,22):
    Wi(k)

def Wi2(k):
    G=Dgraph(k,k+1,k+6)
    GG = G.copy(); GG.delete_vertex(6)
    print( "k,k+6,s,order,W,W-:",k,k+6,k+1,G.order(), \
           G.wiener_index(),GG.wiener_index() )

for k in range(7,23,2):
    Wi2(k)