%0 Journal Article
%T Max-plus objects to study the complexity of graphs
%A Cristiano Bocci
%A Luca Chiantini
%A Fabio Rapallo
%J Mathematics
%D 2011
%I arXiv
%X Given an undirected graph $G$, we define a new object $H_G$, called the mp-chart of $G$, in the max-plus algebra. We use it, together with the max-plus permanent, to describe the complexity of graphs. We show how to compute the mean and the variance of $H_G$ in terms of the adjacency matrix of $G$ and we give a central limit theorem for $H_G$. Finally, we show that the mp-chart is easily tractable also for the complement graph.
%U http://arxiv.org/abs/1111.1352v2