{
  "id": "2001.00740",
  "version": "v1",
  "published": "2020-01-03T06:24:04.000Z",
  "updated": "2020-01-03T06:24:04.000Z",
  "title": "Connectivity and eigenvalues of graphs with given girth or clique number",
  "authors": [
    "Zhen-Mu Hong",
    "Hong-Jian Lai",
    "Zheng-Jiang Xia"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\kappa'(G)$, $\\kappa(G)$, $\\mu_{n-1}(G)$ and $\\mu_1(G)$ denote the edge-connectivity, vertex-connectivity, the algebraic connectivity and the Laplacian spectral radius of $G$, respectively. In this paper, we prove that for integers $k\\geq 2$ and $r\\geq 2$, and any simple graph $G$ of order $n$ with minimum degree $\\delta\\geq k$, girth $g\\geq 3$ and clique number $\\omega(G)\\leq r$, the edge-connectivity $\\kappa'(G)\\geq k$ if $\\mu_{n-1}(G) \\geq \\frac{(k-1)n}{N(\\delta,g)(n-N(\\delta,g))}$ or if $\\mu_{n-1}(G) \\geq \\frac{(k-1)n}{\\varphi(\\delta,r)(n-\\varphi(\\delta,r))}$, where $N(\\delta,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $\\delta$-regular simple graph with girth $g$, and $\\varphi(\\delta,r) = \\max\\{\\delta+1,\\lfloor\\frac{r\\delta}{r-1}\\rfloor\\}$. Analogue results involving $\\mu_{n-1}(G)$ and $\\frac{\\mu_1(G)}{\\mu_{n-1}(G)}$ to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in [Linear Algebra Appl. 439 (2013) 3777--3784], [Linear Algebra Appl. 578 (2019) 411--424], [Linear Algebra Appl. 579 (2019) 72--88], [Appl. Math. Comput. 344-345 (2019) 141--149] and [Electronic J. Linear Algebra 34 (2018) 428--443] are improved or extended.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-01-03T06:24:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C40"
    ],
    "keywords": [
      "clique number",
      "linear algebra appl",
      "eigenvalues",
      "regular simple graph",
      "laplacian spectral radius"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}