Resumen de Reliability of networks modelled by graph products
A general purpose in Graph Theory is to describe any graph structure and provide all the information about it as possible. The study of invariants, properties and graph families of interest has been the aim of many researches in last years. There exist several classical lines of research in Graph Theory which have been extensively investigated. The connectivity is one of them.
The connectivity of a graph represents the minimum number of vertices whose removal disconnects the graph. This notion becomes more relevant when it is applied to networks. The structure of a graph can model whichever type of network so that the reliability of the network is related to the study of the vulnerability of the graph.
We propose one graph family, called strong product graph, and several parameters of great interest as the connectivity, the superconnectivity, the average connectivity, the Menger number, the generalized connectivity and the mean distance. In the present work, we study the mentioned indices on the strong product graph in terms of known invariants of the involved factors and we give some general sharp bounds which are best possible.
A general purpose in Graph Theory is to describe any graph structure and provide all the information about it as possible. The study of invariants, properties and graph families of interest has been the aim of many researches in last years.
There exist several classical lines of research in Graph Theory which have been extensively investigated. The connectivity is one of them.
The connectivity of a graph represents the minimum number of vertices whose removal disconnects the graph. This notion becomes more relevant when it is applied to networks, which is related to the study of the vulnerability in graphs.
Transport and communication, physical, biologic or social networks can be modelled by a graph. For instance, a multiprocessor system, that is, processors communicated by exchanging messages, can be modelled by a graph, where every vertex represents a processor and every edge corresponds to a communication link. To study properties on the graph can provide useful information about the working efficiency of the system.
To select or design a network, many of the requirements correspond to known measures in a graph as the order, the size, the average degree, the diameter or the connectivity, among others. Since it is almost impossible to design an optimal network for all conditions, the selection criteria must be established previously.
One of the most desirable criteria to construct a large interconnection network is joining together the requirements of high reliability and small maximum transmission delay between the nodes of the network. Hence, the priority aim is to get a strong connectivity joint to a suitable diameter in such large graphs.
Another important feature or fundamental principle in networks design is its extendability, that is, the possibility of building larger structures of a network preserving desirable properties.
The graphs products are useful to obtain large graphs from smaller ones whose invariants are known or can be easily calculated. It is well known that the product of graphs are an important topic of research in Graph Theory due to the different applications that one can find in many theoretical contexts.
We propose one graph family, called strong product graph, and several parameters of great interest as the connectivity, the superconnectivity, the average connectivity, the Menger number, the generalized connectivity and the mean distance.
In the present work, we study the mentioned indices on the strong product graph in terms of known invariants of the involved factors and we give some general sharp bounds which are best possible.
