{
  "id": "1612.07103",
  "version": "v1",
  "published": "2016-12-21T13:33:49.000Z",
  "updated": "2016-12-21T13:33:49.000Z",
  "title": "On bipartite cages of excess 4",
  "authors": [
    "Slobodan Filipovski"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The Moore bound $M(k,g)$ is a lower bound on the order of $k$-regular graphs of girth $g$ (denoted $(k,g)$-graphs). The excess $e$ of a $(k,g)$-graph of order $n$ is the difference $ n-M(k,g) $. In this paper we consider the existence of $(k,g)$-bipartite graphs of excess $4$ via studying spectral properties of their adjacency matrices. We prove that the $(k,g)$-bipartite graphs of excess $4$ satisfy the equation $kJ=(A+kI)(H_{d-1}(A)+E)$, where $A$ denotes the adjacency matrix of the graph in question, $J$ the $n \\times n$ all-ones matrix, $E$ the adjacency matrix of a union of vertex-disjoint cycles, and $H_{d-1}(x)$ is the Dickson polynomial of the second kind with parameter $k-1$ and of degree $d-1$. We observe that the eigenvalues other than $\\pm k$ of these graphs are roots of the polynomials $H_{d-1}(x)+\\lambda$, where $\\lambda$ is an eigenvalue of $E$. Based on the irreducibility of $H_{d-1}(x)\\pm2$ we give necessary conditions for the existence of these graphs. If $E$ is the adjacency matrix of a cycle of order $n$ we call the corresponding graphs \\emph{graphs with cyclic excess}; if $E$ is the adjacency matrix of a disjoint union of two cycles we call the corresponding graphs \\emph{graphs with bicyclic excess}. In this paper we prove the non-existence of $(k,g)$-graphs with cyclic excess $4$ if $k\\geq6$ and $k \\equiv1 \\!\\! \\pmod {3}$, $g=8, 12, 16$ or $k \\equiv2 \\!\\! \\pmod {3}$, $g=8,$ and the non-existence of $(k,g)$-graphs with bicyclic excess $4$ if $k\\geq7$ is odd number and $g=2d$ such that $d\\geq4$ is even.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-12-21T13:33:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "adjacency matrix",
      "bipartite cages",
      "bipartite graphs",
      "bicyclic excess",
      "corresponding graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}