Edge-Iterated Independence and Clique Numbers of a Graph and Applications to Design of Sensor Node Networks Contribution Title
摘要
The independence number of a graph G, \(\alpha \left( G \right)\) is the minimum number of pairwise non-adjacent nodes. Let \(\alpha^{1} \left( G \right) = \alpha \left( {L\left( G \right)} \right)\) be the independence number of line graph of G. Let \(\alpha^{2} \left( G \right)\) be the independence number of the line graph of \(L\left( G \right)\) . Continuing like this, we define the nth edge-iterated independence number of the graph G, \(\alpha^{n} \left( G \right)\) as \(\alpha \left( {L^{n} \left( G \right)} \right)\) , the independence number of the nth iterated line graph, \(L^{n} \left( G \right)\) . The clique number of a graph G, \(\omega \left( G \right)\) is the minimum number of pairwise adjacent nodes. Let \(\omega^{1} \left( G \right) = \omega \left( {L\left( G \right)} \right)\) be the clique number of line graph of G. Let \(\omega^{2} \left( G \right)\) be the clique number of the line graph of \(L\left( G \right)\) . Continuing like this, we define the nth edge-iterated clique number of the graph G, \(\omega^{n} \left( G \right)\) as \(\omega \left( {L^{n} \left( G \right)} \right)\) , the clique number of the nth iterated line graph, \(L^{n} \left( G \right)\) . In this paper, we initiate the study of the edge-iterated independence number and edge-iterated clique number and discuss their applications to the fault-tolerance, maintainability and the optimal design of the sensor nodes networks in real-life applications.