Bounds on Laplacian eigenvalues related to total and signed domination of graphs

Wei Shi; Liying Kang; Suichao Wu

Czechoslovak Mathematical Journal (2010)

  • Volume: 60, Issue: 2, page 315-325
  • ISSN: 0011-4642

Abstract

top
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 : V ( G ) { - 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.

How to cite

top

Shi, Wei, Kang, Liying, and Wu, Suichao. "Bounds on Laplacian eigenvalues related to total and signed domination of graphs." Czechoslovak Mathematical Journal 60.2 (2010): 315-325. <http://eudml.org/doc/38009>.

@article{Shi2010,
abstract = {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 \lbrace -1,1\rbrace $ 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.},
author = {Shi, Wei, Kang, Liying, Wu, Suichao},
journal = {Czechoslovak Mathematical Journal},
keywords = {algebraic connectivity; Laplacian matrix; Laplacian spectral radius; signed domination; total domination; algebraic connectivity; Laplacian matrix; Laplacian spectral radius; signed domination; total domination},
language = {eng},
number = {2},
pages = {315-325},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Bounds on Laplacian eigenvalues related to total and signed domination of graphs},
url = {http://eudml.org/doc/38009},
volume = {60},
year = {2010},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 60
IS - 2
SP - 315
EP - 325
AB - 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 \lbrace -1,1\rbrace $ 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.
LA - eng
KW - algebraic connectivity; Laplacian matrix; Laplacian spectral radius; signed domination; total domination; algebraic connectivity; Laplacian matrix; Laplacian spectral radius; signed domination; total domination
UR - http://eudml.org/doc/38009
ER -

References

top
  1. Archdeacon, D., Ellis-Monaghan, J., Fisher, D., Froncek, D., Lam, P. C. B., Seager, S., Wei, B., Yuster, R., 10.1002/jgt.20000, J. Graph Theory 46 (2004), 207-210. (2004) Zbl1041.05057MR2063370DOI10.1002/jgt.20000
  2. Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T., 10.1002/net.3230100304, Networks 10 (1980), 211-219. (1980) Zbl0447.05039MR0584887DOI10.1002/net.3230100304
  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 &amp; Sons (1995), 311-322. (1995) MR1405819
  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. (2003) Zbl1026.05075MR2022276
  5. Feng, L., Yu, G., Li, Q., Minimizing the Laplacian eigenvalues for trees with given domination number, Linear Algebra Appl. 419 (2006), 648-655. (2006) Zbl1110.05060MR2277995
  6. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  7. Grone, R., Merris, R., 10.1137/S0895480191222653, SIAM J. Discrete Math. 7 (1994), 221-229. (1994) Zbl0795.05092MR1271994DOI10.1137/S0895480191222653
  8. Haynes, T. W., Hedetniemi, S. T., Slater, P. J., Fundamentals of Domination in Graphs, Marcel Dekker, New York (1998). (1998) Zbl0890.05002MR1605684
  9. Henning, M. A., Slater, P. J., 10.1016/0012-365X(96)00025-8, Discrete Math. 158 (1996), 87-98. (1996) MR1411112DOI10.1016/0012-365X(96)00025-8
  10. Henning, M. A., 10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F, J. Graph Theory 35 (2000), 21-45. (2000) Zbl0959.05089MR1775793DOI10.1002/1097-0118(200009)35:1<21::AID-JGT3>3.0.CO;2-F
  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. (2005) Zbl1063.05095MR2141097
  12. Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1998), 143-176. (1998) MR1275613
  13. Nikiforov, V., Bounds on graph eigenvalues I, Linear Algebra Appl. 420 (2007), 667-671. (2007) Zbl1109.05073MR2278241

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.