zbMATH — the first resource for mathematics

Eigenvalues and domination in graphs. (English) Zbl 0857.05072
For a finite connected graph \(G\) with \(n\) vertices let \(\gamma(G)\) be the domination number and \(\lambda_n\) the largest eigenvalue of its Laplacian matrix. The authors then establish the following results: (i) If \(\gamma(G)\geq 3\), then \(\lambda_n< n-\lceil{\gamma(G)-2\over 2}\rceil\). (ii) If \(\gamma(G)= 1\), then \(\lambda_n=n\). (iii) If \(\gamma(G)=2\), no better bound than \(\lambda_n\leq n\) exists. (iv) Eigenvectors corresponding to large eigenvalues induce dominating sets in \(G\).

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory
Full Text: EuDML
[1] ANDERSON W. N., MORLEY T. D.: Eigenvalues of the Laplacian of a graph. Linear and Multilinear Algebra 18 (1985), 141-145. · Zbl 0594.05046
[2] FIEDLER M.: Algebraic connectivity in graphs. Czechoslovak Math. J. 23(98) (1973). 298-305. · Zbl 0265.05119
[3] MOHAR B.: The Laplacian spectrum of graphs. Graph Theory, Combinatorics, and Applications (Y. Alavi et al., J. Wiley, New York, 1991, pp. 871-898. · Zbl 0840.05059
[4] MOHAR B., POLJAK S.: Eigenvalues in combinatorial optimization. Preprint 1992. · Zbl 0806.90104
[5] POTHEN A., SIMON H. D., LIOU K.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11 (1990), 430-452. · Zbl 0711.65034
[6] SIMON H. D.: Partitioning of unstructured problems for parallel processing. Computing Sys. Eng. 2 (1991), 135-148.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.