Bounds on graph eigenvalues. I (Q861032): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Import241208061232 (talk | contribs)
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1016/j.laa.2006.08.020 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1016/J.LAA.2006.08.020 / rank
 
Normal rank

Latest revision as of 05:51, 10 December 2024

scientific article
Language Label Description Also known as
English
Bounds on graph eigenvalues. I
scientific article

    Statements

    Bounds on graph eigenvalues. I (English)
    0 references
    0 references
    9 January 2007
    0 references
    The author obtains bounds on the spectral radius of a graph \(G\) and for some eigenvalues of the Laplacian of \(G\). Let \(G=(V,E)\) be a graph of order \(n\). For \(v \in V\), the degree of \(v\) is \(d(v)=| N(v)| \), where \(N(v)\) is the set of vertices adjacent to \(v\). The maximum degree of \(G\) is \(\Delta(G)=\max\{d(v) : v \in V \}\). The author denotes \(\mu(G)=\mu_1(G) \geq \cdots \geq \mu_n(G)\) the eigenvalues of the adjacency matrix of \(G\) and \(0=\lambda_1(G) \leq \cdots \leq \lambda_n(G)=\lambda(G)\) the eigenvalues of the Laplacian matrix of \(G\). Given a graph \(G\), a set \(X \subset V\) is called dominating, if \(N(v) \cap X \neq \emptyset\) for every \(v \in V \backslash X\). The number \(\gamma(G)=\min\{| X| : X\) is a dominating set\} is called the dominating number of \(G\). The main results of the paper establish that if \(G\) is a graph of order \(n \geq 2\) with maximum degree \(\Delta\), and girth at least 5, then \(\mu(G) \leq \min \{\Delta,\sqrt{n-1} \}\). Also, if \(G\) is a graph of order \(n \geq 2\), with dominanting number \(\gamma(G)=\gamma\), then \(\lambda_2(G) \leq n\) if \(\gamma=1\), \(\lambda_2(G) \leq n-\gamma\) if \(\gamma \geq 2\) and \(\lambda_n(G) \geq [n/\gamma]\). The author obtains necessary and sufficient conditions for equality in the above expressions.
    0 references
    spectral radius
    0 references
    domination number
    0 references
    girth
    0 references
    Laplacian
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references