Diamond condition for commuting adjacency matrices of directed and undirected graphs

摘要

In the context of the stability analysis of interdependent networks through the eigenvalue evaluation of theirudadjacency matrices, we characterize algebraically and also geometrically necessary and sufficient conditions for the adjacencyudmatrices of directed and undirected graphs to commute. We alsouddiscuss the problem of communicating the concepts, the theorems,udand the results to a non-mathematical audience, and moreudgenerally across different disciplinary domains, as one of theudfundamental challenges faced by the Internet Science community.udThus, the paper provides much more background, discussion, anduddetail than would normally be found in a purely mathematicaludpublication, for which the proof of the diamond condition wouldudrequire only a few lines. Graphical visualization, examples,uddiscussion of important steps in the proof and of the diamondudcondition itself as it applies to graphs whose adjacency matricesudcommute are provided. The paper also discusses interdependentudgraphs and applies the results on commuting adjacency matricesudto study when the interconnection matrix encoding links betweenudtwo disjoint graphs commutes with the adjacency matrix of theuddisjoint union of the two graphs. Expected applications are inudthe design and analysis of interdependent networks.