In this article we have derived the minimum order of an odd regular graph such that the graph has no matching. We have observed that how it is different from the case of even regular graphs. We have checked the consistency of the derived result with Petersens theorem.
Evolutionary mechanism in a self-organized system cause some functional changes that force to adapt new conformation of the interaction pattern between the components of that system. Measuring the structural differences one can retrace the evolutiona
ry relation between two systems. We present a method to quantify the topological distance between two networks of different sizes, finding that the architectures of the networks are more similar within the same class than the outside of their class. With 43 cellular networks of different species, we show that the evolutionary relationship can be elucidated from the structural distances.
It is basic question in biology and other fields to identify the char- acteristic properties that on one hand are shared by structures from a particular realm, like gene regulation, protein-protein interaction or neu- ral networks or foodwebs, and th
at on the other hand distinguish them from other structures. We introduce and apply a general method, based on the spectrum of the normalized graph Laplacian, that yields repre- sentations, the spectral plots, that allow us to find and visualize such properties systematically. We present such visualizations for a wide range of biological networks and compare them with those for networks derived from theoretical schemes. The differences that we find are quite striking and suggest that the search for universal properties of biological networks should be complemented by an understanding of more specific features of biological organization principles at different scales.
We present the spectrum of the (normalized) graph Laplacian as a systematic tool for the investigation of networks, and we describe basic properties of eigenvalues and eigenfunctions. Processes of graph formation like motif joining or duplication lea
ve characteristic traces in the spectrum. This can suggest hypotheses about the evolution of a graph representing biological data. To this data, we analyze several biological networks in terms of rough qualitative data of their spectra.
The spectrum of the normalized graph Laplacian yields a very comprehensive set of invariants of a graph. In order to understand the information contained in those invariants better, we systematically investigate the behavior of this spectrum under lo
cal and global operations like motif doubling, graph joining or splitting. The eigenvalue 1 plays a particular role, and we therefore emphasize those constructions that change its multiplicity in a controlled manner, like the iterated duplication of nodes.
From the spectral plot of the (normalized) graph Laplacian, the essential qualitative properties of a network can be simultaneously deduced. Given a class of empirical networks, reconstruction schemes for elucidating the evolutionary dynamics leading
to those particular data can then be developed. This method is exemplified for protein-protein interaction networks. Traces of their evolutionary history of duplication and divergence processes are identified. In particular, we can identify typical specific features that robustly distinguish protein-protein interaction networks from other classes of networks, in spite of possible statistical fluctuations of the underlying data.
