Доказательство гипотезы об f-иррегулярных графах для простой цепи Pn

Abstract

Пусть F и G – простые конечные неориентированные графы. Граф G называется F-иррегулярным, если любые две его различные вершины принадлежат различному числу подграфов из G, изоморфных графу F. В 1987 году Чартранд, Холберт, Оеллерман и Сварт выдвинули гипотезу о том, что для каждого связного графа F на трех и более вершинах существует нетривиальный F-иррегулярный граф. Мы подтверждаем эту гипотезу для каждой простой цепи Pn порядка n ≥ 3. Кроме того, для любого целого числа k ≥ 6 мы строим P₄-иррегулярный граф порядка k и показываем, что не существует нетривиального P4-иррегулярного графа на пяти и менее вершинах. = Let F and G be simple, finite, undirected graphs. A graph G is said to be F-irregular if any two of its distinct vertices belong to a different number of subgraphs of G that are isomorphic to F. In 1987, Chartrand, Holbert, Oellermann, and Swart conjectured that for every connected graph F with at least three vertices, there exists a nontrivial F-irregular graph. We confirm this conjecture for every path Pn of order n ≥ 3. In addition, for each integer k ≥ 6, we construct a P₄-irregular graph of order k and show that there does not exist a nontrivial P₄-irregular graph on five or fewer vertices.