The Average Lower 2-Domination Number of Wheels Related Graphs and an Algorithm

[摘要] The problem of quantifying the vulnerability of graphs has received much attention nowadays, especially in the field of computer or communication networks. In a communication network, the vulnerability measures the resistance of the network to disruption of operation after the failure of certain stations or communication links. If we think of a graph as modeling a network, the average lower 2-domination number of a graph is a measure of the graph vulnerability and it is defined byγ2 a v ( G ) =1 |V ( G )| ∑v ∈ V ( G ) γ2 v ( G ) , where the lower 2-domination number, denoted byγ2 v ( G ), of the graph G relative to v is the minimum cardinality of 2-domination set in G that contains the vertex v. In this paper, the average lower 2-domination number of wheels and some related networks namely gear graph, friendship graph, helm graph and sun flower graph are calculated. Then, we offer an algorithm for computing the 2-domination number and the average lower 2-domination number of any graph G.

[学科分类] 计算数学

[关键词] graph vulnerability;connectivity;network design;communication;domination number;average lower 2-domination number