| Title:
|
Bounds on Laplacian eigenvalues related to total and signed domination of graphs (English) |
| Author:
|
Shi, Wei |
| Author:
|
Kang, Liying |
| Author:
|
Wu, Suichao |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
60 |
| Issue:
|
2 |
| Year:
|
2010 |
| Pages:
|
315-325 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
algebraic connectivity |
| Keyword:
|
Laplacian matrix |
| Keyword:
|
Laplacian spectral radius |
| Keyword:
|
signed domination |
| Keyword:
|
total domination |
| MSC:
|
05C50 |
| MSC:
|
05C69 |
| MSC:
|
15A18 |
| idZBL:
|
Zbl 1224.05319 |
| idMR:
|
MR2657951 |
| . |
| Date available:
|
2010-07-20T16:38:32Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140571 |
| . |
| Reference:
|
[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. Zbl 1041.05057, MR 2063370, 10.1002/jgt.20000 |
| Reference:
|
[2] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs.Networks 10 (1980), 211-219. Zbl 0447.05039, MR 0584887, 10.1002/net.3230100304 |
| Reference:
|
[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 1405819 |
| Reference:
|
[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. Zbl 1026.05075, MR 2022276 |
| Reference:
|
[5] Feng, L., Yu, G., Li, Q.: Minimizing the Laplacian eigenvalues for trees with given domination number.Linear Algebra Appl. 419 (2006), 648-655. Zbl 1110.05060, MR 2277995 |
| Reference:
|
[6] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[7] Grone, R., Merris, R.: The Laplacian spectrum of a graph (II).SIAM J. Discrete Math. 7 (1994), 221-229. Zbl 0795.05092, MR 1271994, 10.1137/S0895480191222653 |
| Reference:
|
[8] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs.Marcel Dekker, New York (1998). Zbl 0890.05002, MR 1605684 |
| Reference:
|
[9] Henning, M. A., Slater, P. J.: Inequality relation domination parameters in cube graph.Discrete Math. 158 (1996), 87-98. MR 1411112, 10.1016/0012-365X(96)00025-8 |
| Reference:
|
[10] Henning, M. A.: Graphs with large total domination number.J. Graph Theory 35 (2000), 21-45. Zbl 0959.05089, MR 1775793, 10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F |
| Reference:
|
[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. Zbl 1063.05095, MR 2141097 |
| Reference:
|
[12] Merris, R.: Laplacian matrices of graphs: a survey.Linear Algebra Appl. 197/198 (1998), 143-176. MR 1275613 |
| Reference:
|
[13] Nikiforov, V.: Bounds on graph eigenvalues I.Linear Algebra Appl. 420 (2007), 667-671. Zbl 1109.05073, MR 2278241 |
| . |
