О мерах целостности графов: обзор | ПДМ. 2014. № 4(26).

О мерах целостности графов: обзор

Дан краткий обзор по детерминированным мерам целостности графов. Приводятся известные соотношения между этими мерами и оценки, выраженные через традиционные числовые параметры графа. Меры анализируются с точки зрения сложности вычисления и положенных в их основу моделей повреждения элементов графа, учёта объёма и последствий этих повреждений. Указан ряд открытых проблем.

Measures for graph integrity: a comparative survey.pdf Введение Известно, что в связном графе любые две несовпадающие вершины соединены хотя бы одной цепью. При удалении некоторого множества вершин или рёбер связность графа может быть нарушена. В зависимости от того, сколько и какие элементы удаляются, какими действиями по отношению к исходному графу сопровождаются удаления этих элементов, количественно по-разному может выглядеть результирующий граф с точки зрения числа и размера сформировавшихся компонент связности. Конечно, многое зависит и от структурных особенностей исходного графа. Для учёта и оценки всех этих факторов введено понятие целостности (или живучести) графа [23], которое является обобщением связности. Считается, что более целостным является тот граф, связность которого нарушается при удалении большего числа элементов и последствия этих удалений минимальные (например, результирующий граф имеет достаточно мощную по числу вершин компоненту связности или число компонент в результирующем графе относительно мало) [45]. Для измерения уровня целостности графа применяются количественные показатели, называемые мерами целостности. Исследования по количественной оценке целостности графов начались в 1927 г. с введения понятий вершинной и рёберной связности и доказательств теоремы Менге-ра [9]. Уже предложены и изучены многие детерминированные и вероятностные меры целостности. Эти меры главным образом различаются: - моделью повреждения графа (какие элементы исходного графа удаляются; какими действиями по отношению к исходному графу сопровождаются удаления этих элементов; что представляет собой результирующий граф); - моделью измерения объёма повреждений, то есть числа удаляемых элементов графа (учитывать или нет, и если да, то как); - моделью учёта последствий повреждения графа (учитывать или нет, а если да, то как, через размер наибольшей компоненты связности графа, стоимость нанесенного ущерба или полученного выигрыша и т. п.). Все последние десятилетия и до настоящего времени проблеме исследования мер целостности графов уделяется особое внимание, поскольку она связана с вопросами анализа и синтеза отказоустойчивых сложных технических систем, включая вычислительные системы, коммуникационные и транспортные сети, трубопроводные системы [4, 26, 41]. Для таких систем отказоустойчивость, как правило, является важнейшим показателем качества функционирования [2, 4, 5, 10]. Понятие отказоустойчивости было введено А. Авиженисом [20] как свойство системы сохранять работоспособность (правильность функционирования) при наличии ошибок или отказов. Принято выделять два уровня отказоустойчивости [2]: полная отказоустойчивость - система продолжает работать в случае отказов отдельных ее элементов без существенной потери функциональных свойств; амортизация отказов - система деградирует, то есть сохраняет работоспособность с частичной потерей функций. Полная отказоустойчивость достигается в первую очередь введением избыточности, например, дублированием элементов системы с возможностью замены отказавшего элемента на исправный, который берет на себя соответствующие функции. Избыточность в виде аппаратных, программных, информационных и временных ресурсов является классическим подходом обеспечения отказоустойчивости, который, как правило, ведет к повышению стоимости систем [2, 4, 17]. Поэтому проектирование сложных технических систем - это, прежде всего, поиск компромисса между допустимой стоимостью и требуемой отказоустойчивостью системы. Для решения подобных задач привлекаются различные математические модели и методы оптимизации. В задачах анализа и синтеза отказоустойчивых систем достаточно широко используются методы теории графов и комбинаторной оптимизации [2, 5, 10, 16, 38]. Техническая система представляется в виде связного графа, вершины которого соответствуют элементам системы, а рёбра - связям между элементами. Тогда отказ элемента технической системы можно интерпретировать как удаление надлежащего элемента графа, а потерю связи между элементами - как отсутствие ребра или цепи между соответствующими вершинами графа. В рамках теоретико-графового представления в работе [38] предложена модель для исследования полной отказоустойчивости. При моделировании исходной системы связным графом последний погружается в некоторый минимальный избыточный граф, который рассматривается в качестве отказоустойчивой реализации исходной системы. Минимизация избыточности - одна из основных целей при проектировании отказоустойчивых систем. В рамках этой модели получены многочисленные результаты, представленные в [1, 2, 5, 10, 11, 15, 16] и во многих других работах отечественных и зарубежных авторов. Данные результаты направлены преимущественно на синтез к-отказоустойчивых реализаций систем, где к - наибольшее число одновременных отказов элементов исходной системы. Для исследования амортизации отказов также применяются теоретико-графовые модели и методы. Система считается полностью работоспособной, если соответствующий ей граф связный. Отказы ведут к повреждению надлежащих элементов графа. Меры целостности графа позволяют оценить частичную потерю работоспособности системы вследствие отказа её элементов или связей между ними. Данные меры применяются при решении задач анализа отказоустойчивости технических систем. В данной работе представлен обзор по основным детерминированным мерам целостности графа. Приведены известные соотношения между этими мерами и оценки, выраженные через традиционные числовые параметры графа. Обзор выполнен по научным изданиям, представленным в списке литературы. 1. Основные понятия и обозначения Введём понятия и обозначения теории графов, необходимые для дальнейшего изложения. Все неопределяемые ниже термины можно найти в [9]. Будем рассматривать только простые графы, то есть конечные неориентированные графы без петель и кратных рёбер. Пусть G = (V, E) -простой связный граф с множеством вершин V и множеством рёбер E, при этом n = |V| ^ 1 -порядок графа G. Напомним, что связный граф всегда состоит только из одной компоненты, в которой любые две несовпадающие вершины u и v соединены (u, г^-цепью. При n > 1 две вершины u и v графа G = (V, E) смежны, если {u,v} Е E, и не смежны в противном случае. Ребро e инцидентно вершине u, если e = {u,v} Е E, и не инцидентно иначе. Множество всех вершин графа G = (V, E), смежных с некоторой вершиной v Е V, образует в G окрестность вершины v, которая обозначается через N(v). Под замкнутой окрестностью вершины v Е V в G понимается множество N[v] = N(v) U {v}. Пусть S С V. Тогда множество вершин N(S) = ( IJ N(v) I \ S называется окрестностью, а множество N[S] = N(S) U S - \ves J замкнутой окрестностью для S в графе G. Граф порядка n, в котором любые две вершины смежны, называется полным и обозначается через Kn. Безрёберный граф порядка n обозначается через On. Одновершинный граф O1 (или K1) считается тривиальным. Граф H = (V',E') называется подграфом графа G = (V, E) при условии, что V' С V, E' С E. Если V' = V, то H называется остовным подграфом. Если в H множество вершин есть V', а множество рёбер совпадает с множеством всех рёбер графа G, оба конца которых принадлежат V', то H называется подграфом, порождённым множеством V', и обозначается через G(V'). Такой граф можно получить удалением из G всех вершин, не принадлежащих V', поэтому его обозначают также через G - S, где S = V \ V'. Множество вершин S С V разделяет несмежные вершины u и v графа G = (V, E), если в графе G - S вершины u и v принадлежат различным компонентам связности. Множество S при этом называют (u, v)-сепаратором и минимальным ^^-сепаратором, если в нём нет собственного подмножества, являющегося (u, v)-сепаратором. Сепаратор S минимальный, если в G существует такая пара вершин u и v, что S является минимальным (u, v)-сепаратором, то есть минимальным относительно по крайней мере двух вершин этого графа. Наименьший по мощности сепаратор графа G называется наименьшим. Аналогичным образом определяются разрез (или разделяющее множество рёбер), минимальный и наименьший разрез графа. Необходимо отметить, что при удалении из графа G = (V, E) некоторой вершины v Е V всегда удаляются все рёбра, инцидентные этой вершине. Полученный в результате граф принято обозначать через G - v. Подобным образом определяется граф G - e: он получается из G = (V, E) удалением ребра e = {u,v} Е E, при этом концевые вершины u и v этого ребра остаются в V. Удаление вершины или ребра, а также переход к подграфу - это операции, с помощью которых можно моделировать отказы элементов системы и получать из имеющегося исходного графа другие графы с меньшим числом элементов. Операция добавления ребра, наоборот, позволяет создавать из заданных графов более насыщенные рёбрами графы. Целью такого насыщения может быть увеличение устойчивости сетей к возможным дестабилизирующим факторам. Операция добавления ребра заключается в следующем: если вершины u, v Е V графа G = (V, E) не смежны, то в графе G + e они смежны и соединены ребром e = {u, v}. Далее используются следующие обозначения основных числовых параметров графа G: к(С) -число компонент связности; w(G) -порядок наибольшей (по числу вершин) компоненты связности; 5(G) -минимальная степень вершин; A(G) -максимальная степень вершин; a0(G) и ai(G) -число независимости и число паросочетания соответственно; ei(G) -число рёберного покрытия; x(G) -хроматическое число; 1 или G - S = Oi}, (1) то есть это наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Другими словами, число k(G) задает размер наименьшего сепаратора графа G. Исключение составляет лишь граф Kn, в котором нет сепараторов вообще, хотя к(Кп) = n - 1. Граф /-связен, если k(G) ^ /. Согласно теореме Менгера [9], k(G) ^ / тогда и только тогда, когда любая пара несовпадающих вершин графа G соединена по крайней мере / вершинно-непересекающимися простыми цепями. Аналогичным образом определяется число рёберной связности ^(G) графа G = (V, E): ^(G) = min{|S| : ^G - S) > 1}, ScE то есть ^(G) -это наименьшее число рёбер, удаление которых из G приводит к несвязному графу. По определению число ^(G) определяет размер наименьшего разреза графа G. Граф рёберно-/-связен, если ^(G) ^ /. Из рёберного варианта теоремы Менгера следует, что ^(G) ^ / тогда и только тогда, когда всякая пара несовпадающих вершин графа G связана не менее чем / рёберно-непересекающимися простыми цепями. Значения числовых параметров k(G) и ^(G) применительно к проблеме целостности графа можно интерпретировать так: это объём повреждений (число элементов или связей между элементами графа), после удаления которых граф утрачивает способность поддерживать связь между некоторыми парами вершин. Поэтому чем выше значения k(G) и ^(G), тем более целостным является граф G. Следует отметить, что в данном случае никак не учитывается, сколько компонент содержит граф G-S и каковы размеры этих компонент. При этом для всякого несвязного графа k(G) = ^(G) = 0. Меры связности k(G) и ^(G) хорошо изучены в теории графов. В частности, установлено, что для любого графа G = (V, E), n = | V | ^ 1, верны отношения [9] 0 ^ k(G) ^ MG) ^ 5(G) ^ n - 1. (2) Например, к(Кп) = = 5(Kn) = n - 1 и к(Оп) = ^(On) = 5(On) = 0. Показано, что задача вычисления k(G) и ^(G) для произвольного графа G сводится к задаче о максимальном потоке и минимальном разрезе и является разрешимой за полиномиальное время [12, 13]. Тем не менее вершинная и рёберная связность находят лишь ограниченное применение в анализе отказоустойчивости систем, поскольку в них учитывается лишь объём повреждений и игнорируются многие важные факторы, связанные с последствиями повреждений. В настоящее время для учёта подобных факторов предложены и изучены другие числовые параметры графа. 3. Вершинная и рёберная целостность Понятия вершинной и рёберной целостности были введены в 90-е годы XX столетия К. Багга, К. Барфутом, Р. Энтрингером и Г. Свортом [21-23]. На сегодняшний день это наиболее изученные меры целостности графа. Под вершинной целостностью (vertex integrity) графа G = (V, E) понимается числовой параметр I(G), вычисляемый по формуле I (G)=min{|S | + w(G - S)}, (3) где w(G - S) - порядок наибольшей компоненты связности графа G - S. Заметим, что формула (3) применима как для связного, так и для несвязного графа. Согласно (3), вершинная целостность графа выражается через сумму двух слагаемых: - число |S| удаляемых вершин. Характеризует объём повреждений; - порядок w(G - S) самой крупной компоненты графа G - S, в границах которой взаимные связи между вершинами ещё возможны. Отражает, насколько сильно повреждён граф. Считается, что всякая вышедшая из строя вершина v Е S не может поддерживать связи с другими вершинами, поэтому она удаляется из графа G вместе с инцидентными ей рёбрами. В результате получается граф G - v. Одновременное повреждение всех вершин из S С V приводит к подграфу G - S графа G, который представляет собой работоспособную часть системы, состоящую из одного или более фрагментов. Величина w(G - S) характеризует размер самого крупного фрагмента системы, который образовался после выхода из строя сразу всех вершин из S. Из (1) и (3) следует, что вершинная целостность I(G) как мера целостности графа является обобщением k(G), учитывающим не только объём повреждений, но и последствия повреждений в виде порядка самой крупной компоненты графа G - S. Ясно, что чем выше значение I(G), тем более целостным или живучим является граф G. Утверждение 1. Для любого графа G = (V, E) справедливы высказывания: а) если v Е V, то I(G - v) ^ I(G); б) если e Е E, то I(G - e) ^ I(G); в) если u,v Е V, то I(G) ^ I(G + e), где e = {u, v}; г) если H есть подграф графа G, то I(H) ^ I(G). Высказывания, сформулированные в утверждении 1, очевидным образом следуют из определения вершинной целостности и соответствующих операций над графами. Утверждение 1 свидетельствует, что удаление отдельных элементов графа может снижать его вершинную целостность. Например, I(Kn) = n и I(On) = 1. Очевидно, что любой граф порядка n можно получить удалением из Kn некоторых, а возможно, и всех его рёбер. Поэтому в общем случае для вершинной целостности графа G = (V, E) верны естественные границы: 1 ^ I(G) ^ n, n = |V| ^ 1. Наибольшее значение вершинной целостности достигается на полном графе, а наименьшее - на безрёберном графе. Из утверждения 1 также следует, что вершинная целостность всякого остовно-го подграфа графа G не выше вершинной целостности графа G в целом. Обозначим через W(S) = |S| + w(G - S) значение целевой функции в (3) при заданном множестве S. Отсюда I (G) = min W (S) SCV и для любого S С V I(G) ^ W(S) = |S| + w(G - S). В частности, при S = 0 всегда I(G) ^ w(G - S) = w(G). Множество S, для которого достигается минимум W (S), то есть I (G) = |S | + + w(G - S), принято называть I-множеством. Для заданного графа может существовать несколько I-множеств. Наименьшее по мощности I-множество называется наименьшим. Очевидно, что для связного графа G = (V, E) при S = 0 или S = V всегда W(S) = n. Кроме того, если S не является сепаратором графа G, то также W(S) = n. Значит, если связный граф G неполный, то минимум W(S) может достигаться только на сепараторах этого графа G. Другими словами, в неполном связном графе G всякое I-множество является сепаратором G и, следовательно, содержит не менее k(G) вершин. Другое важное с вычислительной точки зрения свойство I-множества сформулировано в следующем утверждении, детали доказательства которого приведены в [37]. Утверждение 2. Для любого связного нетривиального графа G = (V, E) I(G) = 1 + min I(G - v). (4) v€V Для нетривиального графа, который не обязательно связен, формула (4) принимает вид I(G) = min < 1 + min I(G - v),w(G) I v€V Пусть Gv = G - v, v E V. Систему {Gv : v E V} подграфов принято называть колодой графа G = (V, E) [9]. Таким образом, утверждение 2 указывает рекуррентный способ вычисления вершинной целостности графа через его колоду. Как отмечено выше, число вершинной связности k(G) определяет размер наименьшего по мощности сепаратора графа G, а I-множества в неполном связном графе G обязательно являются сепараторами. Следовательно, справедливо неравенство k(G) + 1 ^ I(G), (5) которое задаёт нижнюю оценку целостности графа. Оценка (5) выполняется для любого графа, так как, согласно (2), всегда k(G) ^ 5(G) и 5(G) + 1 ^ I(G). (6) Правильность (6) основана на следующих рассуждениях. Для всякого I-множества графа G верны отношения w(G - S) ^ 5(G - S) + 1 ^ 5(G) - |S| + 1, поэтому I(G) = |S| + w(G - S) ^ 5(G) + 1. Примечательно, что нижние оценки (5), (6) вычисляются за полиномиальное время. Используя (6), можно получить другие нижние оценки. В частности, всегда x(G) ^ I(G). (7) Действительно, если x(G) = r, то в графе G существует порождённый подграф H, для которого 6(H) ^ r - 1. По утверждению 1 имеем I(G) ^ I(H) ^ 5(H) + 1 ^ r = x(G), что подтверждает (7). Из известного неравенства

Ключевые слова

графы, целостность, прочность, число рассеяния, стойкость, степень разрушения, окрестная целостность, доминирующая целостность, graphs, vulnerability, integrity, toughness, scattering number, tenacity, rupture degree, domination integrity, network reliability, neighbour integrity

Авторы

ФИООрганизацияДополнительноE-mail
Быкова Валентина ВладимировнаИнститут математики и фундаментальной информатики Сибирского федерального университета, г. Красноярскдоктор физико-математических наук, доцент, профессорbykvalen@mail.ru
Всего: 1

Ссылки

Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2004. №88(5). С. 643-650.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012.
Быкова В. В. FPT-алгоритмы и их классификация на основе эластичности // Прикладная дискретная математика. 2011. №2(12). С. 40-48.
Громов Ю. Ю., Драчёв В. О., Набатов К. А., Иванова О. Г. Синтез и анализ живучести сетевых систем. М.: Машиностроение, 2007.
Грязнов Н. Г., Димитриев Ю. К., Мелентьев В. А. Оптимизация отказоустойчивого вложения диагностического графа в тороидальные структуры живучих вычислительных систем // Автоматика и телемеханика. 2003. №4. С. 133-152.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Дундар П., Айтак А. Выражения целостности тотальных графов через некоторые характеристики графов // Матем. заметки. 2004. №76(5). С. 714-722.
Дундар П., Айтак А., Айтак В. Вычисление индекса доступности и окрестной целостности графа // Матем. заметки. 2005. №78(5). С. 676-686.
Емеличев В. А, Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Книжный дом «ЛИБРОКОМ», 2012.
Каравай М. Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // Автоматика и телемеханика. 1996. №6. С. 159-173.
Каравай М. Ф. Инвариантно-групповой подход к исследованию k-отказоустойчивых структур // Автоматика и телемеханика. 2000. №1. С. 144-156.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильямс, 2012.
Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978.
Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.
Салий В. Н Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1(1). С. 116-119.
Салий В. Н Оптимальные реконструкции графов // Современные проблемы дифференц. геометрии и общей алгебры. Саратов: Изд-во Сарат. ун-та, 2008. С. 59-65.
Хорошевский В. Г. Архитектура вычислительных систем. М.: МГТУ им. Н. Э. Баумана, 2008.
Atici M., Crawford R., and Ernst C. New upper bounds for the integrity of cubic graphs // Int. J. Computer Math. 2004. No. 81(11). P. 1341-1348.
Atici M., Crawford R., and Ernst C. The integrity of small cage graphs // Australasian J. Combinatorics. 2009. No. 43. P. 39-55.
Avizienis A. The design of fault tolerant computers // AFIPS Conf. Proc. NY, USA, 1967. P. 733-743.
Bagga K. S., Beineke L. W., Goddard W.D., et al. A survey of integrity // Discrete Appl. Math. 1992. No. 37/38. P. 13-28.
Bagga K.S., Beineke L.W., Lipman M. J., and Pippert R. E. Edge-integrity: a survey // Discrete Math. 1994. V. 124. P. 3-12.
Barefoot C. A., EntringerR., and Swart H. C. Vulnerability in graphs - a comparative survey // J. Combin. Math. Combin. Comput. 1987. No. 1. P. 13-22.
Barefoot C. A., Entringer R., and Swart H. C. Integrity of trees and powers of cycles // Congr. Numer. 1987. V. 58. P. 103-114.
Bauer D., Hakimi S. L., and Schmeichel E. Recognizing tough graphs is NP-hard // Discrete Appl. Math. 1990. V.28. P. 191-195.
Bodlaender H. L., Hendriks A., Grigoriev A., and Grigorieva N. V. The valve location problem in simple network topologies // Informs. J. Computing. 2010. V. 22(3). P. 433-442.
Bykova V. V. Parameterized complexity and elasticity of the algorithms // Proc. 14th Appl. Stochastic Models and Data Analysis Int. Conf. (ASMDA2011). Rome, Italy, 2011. P. 219-225.
Bykova V. V. Analysis parameterized algorithms on the bases of elasticity to functions complexity // J. Siberian Federal University. Math. & Physics. 2011. No. 4(2). P. 195-207.
Chvatal V. Tough graphs and Hamiltonian circuits // Discrete Math. 1973. No. 5. P. 215-228.
Clark L. H., Entringer R. C., and Fellows M. R. Computational complexity of integrity //J. Combin. Math. Combin. Comput. 1987. No. 2. P. 179-191.
CozzensM.B. and WuS.Y. Vertex-neighbor-integrity of trees // Ars Combinator. 1996. V. 43. P. 169-180.
Cozzens M. B. and Wu S. Y. Bounds of edge-neighbor-integrity of graphs // Australasian J. Combinatorics. 1997. V. 15. P. 71-80.
DeLaViaE., Pepper R., and Waller B. Lower bounds for the domination number // Discussiones Math. Graph Theory. 2010. V.30(3). P. 475-487.
Downey R. G. and Fellows M. R. Parameterized complexity. N.Y.: Springer Verlag, 1999.
Drange P. G., Dregi M. S., and Hof P. On the computational complexity of vertex integrity. 2014. http://arxiv.org/abs/1403.6331v1.
Fellows M. and Stueckle S. The immersion order, forbidden subgraphs and the complexity of network integrity //J. Combin. Math. Combin. Comput. 1989. No. 6. P. 23-32.
Goddard W. and Swart H. C. Integrity in graphs: bounds and basic //J. Combin. Math. Combin. Comput. 1990. No. 7. P. 139-151.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V. 25(9). P. 875-884.
Katona G. Y. Toughness and edge-toughness // Discrete Math. 1997. V. 164. P. 187-196.
Kratsch D., Kloks T., and Muller H. Measuring the vulnerability for classes of intersection graphs // Discrete Appl. Math. 1997. V.77(3). P. 259-270.
Laporte G. and Pascoal M. The pipeline and valve location problem // Eur. J. Industr. Eng. 2012. No. 6(3). P. 301-321.
Li F. W. and LiX.L. Computing the rupture degrees of graphs // Proc. 7th Int. Symp. Parallel Architectures, Algorithms and Networks, IEEE Computer Society. Los Alamitos, California, 2004. P. 368-373.
Li Y., Zhang S., and Zhang Q. Vulnerability parameters of split graphs // Int. J. Comput. Math. 2008. V.85(1). P. 19-23.
Mann D. E. The tenacity of trees. Ph. D. Thesis. Northeastern University, 1993.
Moazzami D. Vulnerability in graphs - a comparative survey // J. Combin. Math. Combin. Comput. 1999. V.30. P. 23-31.
Moazzami D. An algorithm for the computation of edge integrity, I'(T) // Int. J. Contemp. Math. Sci. 2011. No. 6(11). P. 507-516.
Ray S. and Deogun J. S. Computational complexity of weighted integrity // J. Combin. Math. Combin. Comput. 1994. V. 16. P. 65-73.
Ray S., Kannan R., Zhang D., and Jiang H. The weighted integrity problem is polynomial for interval graphs // Ars Combinator. 2006. V. 79. P. 77-95.
Sundareswaran R. and Swaminathan V. Domination integrity in graphs // Proc. Int. Conf. Math. Exp. Physics. Prague, Narosa Publishing House, 2009. P. 46-57.
Sundareswaran R. and Swaminathan V. Domination integrity of powers of cycles // Int. J. Math. Res. 2011. No. 3(3). P. 257-265.
Sundareswaran R. and Swaminathan V. Domination integrity in trees // Bulletin Int. Math. Virtual Institute. 2012. No. 2. P. 153-161.
Piazza B. L., Robertst F. S., and Stueckle S. K. Edge-tenacious networks // Networks. 1995. V. 25. P. 7-17.
Vaidya S. K. and Shah N. H. Domination integrity of total graphs // TWMS J. App. Eng. Math. 2011. No. 4(1). P. 117-126.
Vaidya S. K. and Kothari N. J. Some new results on domination integrity of graphs // Open J. Discrete Math. 2012. No. 2(3). P. 96-98. http://dx.doi.org/10.4236/ojdm.2012.23018
Vince A. The integrity of a cubic graph // Discrete Appl. Math. 2004. V. 140(1-3). P. 223-239.
Woeginger G. J. The toughness of split graphs // Discrete Math. 1998. V. 190(1-3). P. 295-297.
Ye Q. On vulnerability of power and total graphs // WSEAS Trans. Math. 2012. No. 11. P. 1028-1038.
Zhang Q. L. and Zhang S. G. Edge vulnerability parameters of split graphs // Appl. Math. Lett. 2006. V. 19. P. 916-920.
Zhang S. G., Li X. L., and Han X. L. Computing the scattering number of graphs // Int. J. Comput. Math. 2002. V.79(2). P. 179-187.
 О мерах целостности графов: обзор | ПДМ. 2014. № 4(26).

О мерах целостности графов: обзор | ПДМ. 2014. № 4(26).