Geodesic
Bounds on Laplacian eigenvalues related to total and signed domination of graphs
Czechoslovak Mathematical Journal, Tome 60 (2010) no. 2, pp. 315-325 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A total dominating set in a graph $G$ is a subset $X$ of $V(G)$ such that each vertex of $V(G)$ is adjacent to at least one vertex of $X$. The total domination number of $G$ is the minimum cardinality of a total dominating set. A function $f\colon V(G)\rightarrow \{-1,1\}$ is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of $G$ is the minimum weight of an SDF on $G$. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.
A total dominating set in a graph $G$ is a subset $X$ of $V(G)$ such that each vertex of $V(G)$ is adjacent to at least one vertex of $X$. The total domination number of $G$ is the minimum cardinality of a total dominating set. A function $f\colon V(G)\rightarrow \{-1,1\}$ is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of $G$ is the minimum weight of an SDF on $G$. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.
Classification : 05C50, 05C69, 15A18
Keywords: algebraic connectivity; Laplacian matrix; Laplacian spectral radius; signed domination; total domination 
@article{CMJ_2010_60_2_a1,
     author = {Shi, Wei and Kang, Liying and Wu, Suichao},
     title = {Bounds on {Laplacian} eigenvalues related to total and signed domination of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {315--325},
     year = {2010},
     volume = {60},
     number = {2},
     mrnumber = {2657951},
     zbl = {1224.05319},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2010_60_2_a1/}
}
TY  - JOUR
AU  - Shi, Wei
AU  - Kang, Liying
AU  - Wu, Suichao
TI  - Bounds on Laplacian eigenvalues related to total and signed domination of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2010
SP  - 315
EP  - 325
VL  - 60
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2010_60_2_a1/
LA  - en
ID  - CMJ_2010_60_2_a1
ER  - 
%0 Journal Article
%A Shi, Wei
%A Kang, Liying
%A Wu, Suichao
%T Bounds on Laplacian eigenvalues related to total and signed domination of graphs
%J Czechoslovak Mathematical Journal
%D 2010
%P 315-325
%V 60
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2010_60_2_a1/
%G en
%F CMJ_2010_60_2_a1
Shi, Wei; Kang, Liying; Wu, Suichao. Bounds on Laplacian eigenvalues related to total and signed domination of graphs. Czechoslovak Mathematical Journal, Tome 60 (2010) no. 2, pp. 315-325. http://geodesic.mathdoc.fr/item/CMJ_2010_60_2_a1/

[1] Archdeacon, D., Ellis-Monaghan, J., Fisher, D., Froncek, D., Lam, P. C. B., Seager, S., Wei, B., Yuster, R.: Some remarks on domination. J. Graph Theory 46 (2004), 207-210. | DOI | MR | Zbl

[2] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980), 211-219. | DOI | MR | Zbl

[3] Dunbar, J. E., Hedetniemi, S. T., Henning, M. A., Slater, P. J.: Signed domination number of a graph. In: Graph Theory, Combinatorics, and Applications, John Wiley & Sons (1995), 311-322. | MR

[4] Fallat, S. M., Kirkland, S., Pati, S.: On graphs with algebraic connectivity equal to minimum edge density. Linear Algebra Appl. 373 (2003), 31-50. | MR | Zbl

[5] Feng, L., Yu, G., Li, Q.: Minimizing the Laplacian eigenvalues for trees with given domination number. Linear Algebra Appl. 419 (2006), 648-655. | MR | Zbl

[6] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | MR | Zbl

[7] Grone, R., Merris, R.: The Laplacian spectrum of a graph (II). SIAM J. Discrete Math. 7 (1994), 221-229. | DOI | MR | Zbl

[8] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR | Zbl

[9] Henning, M. A., Slater, P. J.: Inequality relation domination parameters in cube graph. Discrete Math. 158 (1996), 87-98. | DOI | MR

[10] Henning, M. A.: Graphs with large total domination number. J. Graph Theory 35 (2000), 21-45. | DOI | MR | Zbl

[11] Lu, M., Liu, H., Tian, F.: Bounds of Laplacian spectrum of graphs based on the domination number. Linear Algebra Appl. 402 (2005), 390-396. | MR | Zbl

[12] Merris, R.: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197/198 (1998), 143-176. | MR

[13] Nikiforov, V.: Bounds on graph eigenvalues I. Linear Algebra Appl. 420 (2007), 667-671. | MR | Zbl