Max-Plus Objects to Study the Complexity of Graphs

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.