Regular factors of regular graphs from eigenvalues (Q612943)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Regular factors of regular graphs from eigenvalues
scientific article

    Statements

    Regular factors of regular graphs from eigenvalues (English)
    0 references
    0 references
    16 December 2010
    0 references
    Summary: Let \(r\) and \(m\) be two integers such that \(r\geq m\). Let \(H\) be a graph with order \(|H|\), size \(e\) and maximum degree \(r\) such that \(2e\geq |H|r-m\). We find a best lower bound on the spectral radius of a graph \(H\) in terms of \(m\) and \(r\). Let \(G\) be a connected \(r\)-regular graph of order \(|G|\) and \(k<r\) be an integer. Using the previous results, we find some best upper bounds (in terms of \(r\) and \(k\)) on the third largest eigenvalue that is sufficient to guarantee that \(G\) has a \(k\)-factor when \(k|G|\) is even. Moreover, we find a best bound on the second largest eigenvalue that is sufficient to guarantee that \(G\) is \(k\)-critical when \(k|G|\) is odd. Our results extend the work of \textit{S.M. Cioabă}, \textit{D.A. Gregory} and \textit{W.H. Haemers} [J. Comb. Theory, Ser. B 99, No.\,2, 287--297 (1999; Zbl 1205.05177)] who obtained such results for 1-factors.
    0 references
    lower bound
    0 references
    best upper bound
    0 references
    third largest eigenvalue
    0 references
    second largest eigenvalue
    0 references

    Identifiers