Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On bipartite cages of excess 4 [Elektronski vir]
    Filipovski, Slobodan
    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$▫ by studying spectral properties of their adjacency matrices. For a given graph ▫$G$▫ and for the integers ▫$i$▫ with ▫$0 \leq i \leq diam(G)$▫, the ▫$i$▫- distance matrix ▫$A_i$▫ of ▫$G$▫ is an ▫$n \times n$▫ matrix such that the entry in position ▫$(u,v)$▫ is ▫$1$▫ if the distance between the vertices ▫$u$▫ and ▫$v$▫ is ▫$i$▫, and zero otherwise. We prove that the ▫$(k,g)$▫-bipartite graphs of excess ▫$4$▫ satisfy the equation ▫$kJ = (A+kI)(H_{d-1}(A)+E)$▫, where ▫$A = A_{1}$▫ denotes the adjacency matrix of the graph in question, ▫$J$▫ the ▫$n \times n$▫ all-ones matrix, ▫$E=A_{d+1}$▫ 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 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)\pm 2$▫, 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 graphs with cyclic excess ; if ▫$E$▫ is the adjacency matrix of a disjoint union of two cycles, we call the corresponding graphs 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 \geq 7$▫ is an odd number and ▫$g = 2d$▫ such that ▫$d \geq 4$▫ is even.
    Vir: The Electronic journal of combinatorics [Elektronski vir]. - ISSN 1077-8926 (Vol. 24, iss. 1, 2017, P1.40 (12 str.))
    Vrsta gradiva - e-članek
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 17946969

    Povezava(-e):

    http://www.combinatorics.org/ojs/index.php/eljc/article/download/v24i1p40/pdf

Vnos na polico