{
  "id": "1111.1352",
  "version": "v2",
  "published": "2011-11-05T21:38:29.000Z",
  "updated": "2011-11-08T10:16:25.000Z",
  "title": "Max-plus objects to study the complexity of graphs",
  "authors": [
    "Cristiano Bocci",
    "Luca Chiantini",
    "Fabio Rapallo"
  ],
  "comment": "16 pages, 7 figures. 2 figures were not displayed properly in the first version",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-11-08T10:16:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "60F05"
    ],
    "keywords": [
      "max-plus objects",
      "complexity",
      "central limit theorem",
      "complement graph",
      "max-plus algebra"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1111.1352B"
    }
  }
}