On bipartite cages of excess 4

MaRDI QIDQ521356zbMATH OpenFDO

Authors Slobodan Filipovski

Publication date 10 April 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.07103, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p40

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bicyclic excessbipartite graphscage problemcyclic excess

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

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 $nimesn$ 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 $pmk$ 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 $kgeq6$ and $kequiv1!!pmod3$, $g=8,12,16$ or $kequiv2!!pmod3$, $g=8,$ and the non-existence of $(k,g)$-graphs with bicyclic excess $4$ if $kgeq7$ is odd number and $g=2d$ such that $dgeq4$ is even.

Review text

Summary: 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 \mathrm{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\geq 6\) and \(k \equiv 1\) (mod 3), \(g=8, 12, 16\) or \(k \equiv 2\) (mod 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.

Recommendations

• scientific article; zbMATH DE number 1161321
• scientific article; zbMATH DE number 1472092
• C₄-saturated bipartite graphs
• scientific article; zbMATH DE number 2188443
• On 4-regular 4-connected bipancyclic subgraphs of hypercubes
• On the order of bi-regular cages of even girth
• Congruences for bipartition and partition triples with 4-core
• On the universal partition theorem for 4-polytopes
• Cayley graphs and symmetric 4-polytopes
• On cages with given degree sets

Cites work

• A note on the upper bound and girth pair of (\(k;g\))-cages
• Dynamic cage survey
• Graphs with even girth and small excess
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• scientific article; zbMATH DE number 3412694 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• Improved lower bounds for the orders of even girth cages
• On almost distance-regular graphs
• On bipartite graphs of defect 2
• On graphs with cyclic defect or excess
• On graphs with excess or defect 2
• On Minimal graphs of maximum even girth
• Regular graphs with excess one
• Regular Graphs with Given Girth and Restricted Circuits
• The non-existence of certain regular graphs of girth 5

Cited in

(9)

• On the non-existence of antipodal cages of even girth
• On biregular bipartite graphs of small excess
• scientific article; zbMATH DE number 1161321 (Why is no real title available?)
• scientific article; zbMATH DE number 1472092 (Why is no real title available?)
• Counting cycles in graphs with small excess
• On graphs with cyclic defect or excess
• On a relation between bipartite biregular cages, block designs and generalized polygons
• New results on bipartite biregular cages, block designs, and generalized polygons
• Biregular (and regular) planar cages

This page was built for publication: On bipartite cages of excess 4

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521356)